POJ 4117 简单的数字划分问题

题目

总时间限制: 100ms 内存限制: 65536kB

描述

将正整数n 表示成一系列正整数之和，n=n1+n2+…+nk, 其中n1>=n2>=…>=nk>=1 ，k>=1 。

正整数n 的这种表示称为正整数n 的划分。正整数n 的不同的划分个数称为正整数n 的划分数。

输入

标准的输入包含若干组测试数据。每组测试数据是一个整数N(0 < N <= 50)。

输出

对于每组测试数据，输出N的划分数。

样例输入

5

样例输出

7

提示

5, 4+1, 3+2, 3+1+1, 2+2+1, 2+1+1+1, 1+1+1+1+1

解题思路：典型的动态规划中的完全背包问题

若输入的数字为5，则可以看作其中包含5个物品，value分别为1，2，3，4，5

每个物品可以选择多次，最终将选择的物品的value累加得数字5

可以使用一个一维的滚动数组

状态转移方程：dp[j]=dp[j-i]+dp[j]

    int N;
    cin >> N;

    vector<int> dp(N+1);

    dp[0] = 1;

    for(int i=1;i<=N;++i)

            for (int j = i; j <= N; ++j)

            {

                dp[j] = dp[j - i] + dp[j];

            }

    cout << dp[N] << endl;

    return 0;

特别地，如果每个数字只能取一次，即改为01背包问题，只需将j改为递减

for (int j = N; j >= i; --j)