A positive integer n is given. It is required to find the number of ways to represent it as the sum of odd terms. Moreover, partitions differing only in the order of the terms are considered to be the same. They said that they should be solved using the “dynamic programming method”, I have been sitting for an hour, I can’t figure it out, please help, you can just use an algorithm or some explanation. Thank you in advance :)

  • one
    Read [this] [1] [1]: fvn2009.narod.ru/Olympiads/Rules_Olympiads/Rules24.htm - Nitive
  • @akisha is, though not exactly C ++, but. If the terms cannot be the same, then fn = 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 one units - alexlz
  • @alexlz, you just need to find the number of methods, without generating them and displaying them on the screen - akisha
  • @akisha fn = length $ filter (/ = []) $ f '[] 0 [1,3 ..] where and hereinafter. In general, it is not entirely clear what side dynamic programming is here. Normal search with return. Well, if you need to analytically derive the result of the dependence on the number n - so this is a completely different discipline. - alexlz
  • 2
    Everything stopped again before dawn ... #include <iostream> 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; } Option hs fn = 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 - alexlz

0