4117:简单的整数划分问题（动态规划）

 1 //解题思路：典型的动态规划中的完全背包问题
 2 //若输入的数字为5，则可以看作其中包含5个物品，value分别为1，2，3，4，5
 3 //每个物品可以选择多次，最终将选择的物品的value累加得数字5
 4 //可以使用一个一维的滚动数组
 5 //状态转移方程：dp[j]=dp[j-i]+dp[j]
 6 #include<bits/stdc++.h>
 7 using namespace std;
 8 int main() {
 9     int N;
10     while(cin >> N) {
11         int dp[1010];
12         memset(dp,0,sizeof(dp));
13         dp[0] = 1;
14         for(int i=1; i<=N; ++i)
15             for (int j = i; j <= N; ++j) {
16                 dp[j] = dp[j - i] + dp[j];
17             }
18         cout << dp[N] << endl;
19     }
20     return 0;
21 }