Home>

A positive integer n is specified. It is required to find the number of ways represent it as a sum of odd terms. In this case, the partitions differing only in the order of the terms are considered the same. They said to solve it "by the method of dynamic programming", I've been sitting for an hour now, I can't figure it out, please help, you can just use an algorithm, or some explanations. Thank you in advance :)

Read [this] [1] [1]: fvn2009.narod.ru/Olympiads/Rules_Olympiads/Rules24.htm

Nitive2021-03-06 12:13:31

@akisha this is not really c++, but. If the terms cannot be the same, then f n= filter (/= []) $ f '[] 0 [1,3 ..] where f' s sumS (l: ls) | sumS + l== n= [reverse $ l: s] | sumS + l>n= [[]] | otherwise= f '(l: s) (sumS + l) ls ++ f' s sumS ls If they can, then f 'changes to f' s sumS (l: ls) | sumS + l== n= [reverse $ l: s] | sumS + l>n= [[]] | otherwise= f '(l: s) (sumS + l) (l: ls) ++ f' s sumS But in this case, the first will be a list of all ones

alexlz2021-03-06 12:13:31

@alexlz, you just need to find the number of ways, without generating and displaying them

akisha2021-03-06 12:13:31

@akisha f n= length $ filter (/= []) $ f '[] 0 [1,3 ..] where and further in the text. In general, it is not entirely clear how dynamic programming is here. Normal search and return. Well, if you need to analytically deduce the dependence of the result on the number n, then this is a completely different discipline.

alexlz2021-03-06 12:13:31

Everything froze until dawn again ... #include int akisha (int n, int sumS, int oddNumber) {if (sumS + oddNumber== n) return 1; if (sumS + oddNumber>n) return 0; return akisha (n, sumS + oddNumber, oddNumber + 2) + akisha (n, sumS, oddNumber + 2); } int main () {int n; std :: cin >>n; std :: cout << akisha (n, 0, 1) << std :: endl; } Variant hs f n= f '0 1 where f' sumS oddN | sumS + oddN== n= 1 | sumS + oddN>n= 0 | otherwise= f '(sumS + oddN) o + f' sumS o where o= oddN + 2

alexlz2021-03-06 12:13:31