题目1：

如果我们打算将一个给定的正整数 N ( N ≤ 50 ) N(N≤50) N(N≤50)拆分为若干个不重复的正整数 ( a 1 + a 2 + ⋯ a i , i ≥ 1 ) (a_1+a_2+⋯a_i,i≥1) (a1+a2+⋯ai,i≥1)之和，其中每个零数的取值不大于给定的正整数 M ( M ≤ 20 ) M (M≤20) M(M≤20)，即 1 ≤ a i ≤ M 1≤a_i≤M 1≤ai≤M，请问共有多少种不同的拆分方案。

法一： DFS搜索。

#include <iostream>
using namespace std;
int t, n, m, ans;
void dfs(int sum, int a) {
          
   
    if (sum == n)
        ans++;
    if (sum >= n)
        return;
    for (int j = a + 1; j <= m; j++)
        dfs(sum + j, j);
    return;
}

int main() {
          
   
    cin >> t;
    for (int k = 0; k < t; k++) {
          
   
        cin >> n >> m;
        ans = 0;
        for (int i = 1; i <= m; i++) {
          
   
            dfs(i, i);
        }
        cout << "case #" << k << ":
" << ans << endl;
    }
    return 0;
}

法二： 动态规划：一维数组。 思路：设已知里面有一个数是i，把i剥离出来的划分方式依然是满足条件的划分方式。注意是倒着循环。构建 d p [ n + 1 ] dp[n+1] dp[n+1]数组，下标代表“背包容量”。

#include <cstring>
#include <iostream>
using namespace std;
int t, n, m;
int dp[55];

int main() {
          
   
    cin >> t;
    for (int i = 0; i < t; i++) {
          
   
        cin >> n >> m;
        memset(dp, 0, sizeof(dp));
        dp[0] = 1;
        for (int i = 1; i <= m; i++)
            for (int j = n; j >= i; j--)
                dp[j] += dp[j - i];
        cout << "case #" << i << ":
" << dp[n] << endl;
    }
    return 0;
}

法三： 动态规划，二维数组。 思路： （1）当n=1，无论m为多少，只有一种划分。 （2）当m=1，无论n为多少，只有一种划分。 （3）当n<m，一种。 （4）当n=m，如果划分中有n，则只有{n}一种划分；当划分中没有n，则 f （ n ， n ） = f （ n ， n − 1 ） f（n，n）=f（n，n-1） f（n，n）=f（n，n−1） 故： f （ n ， n ） = 1 + f ( n ， n − 1 ) f（n，n）= 1 + f(n，n - 1) f（n，n）=1+f(n，n−1) （5）当n>m，如果划分中有m，则 m ， x 1 ， x 2 ， … = n − m ， f （ n ， m ） = f （ n − m ， m ） {m，{x1，x2，…} = n - m}，f（n，m）=f（n - m， m） m，x1，x2，…=n−m，f（n，m）=f（n−m，m）；当划分中没有m， f （ n ， m ） = f （ n ， m − 1 ） f（n，m）=f（n，m - 1） f（n，m）=f（n，m−1）。 故： f （ n ， m ） = f （ n − m ， m ） + f （ n ， m − 1 ） f（n，m） = f（n - m， m）+ f（n，m - 1） f（n，m）=f（n−m，m）+f（n，m−1） 核心代码：

int dp[n][m];
//solve部分
for(int i = 1; i <= n; i++){
          
   
	for(int j = 1; j <= m; j++ ){
          
   
         if(i == 1 || j == 1)dp[i][j] = 1;
         else if (i == j) dp[i][j] = 1 + dp[i][j - 1];
         else if (i < j) dp[i][j] = dp[i][i];
         else
              dp[i][j] = dp[i - j][j] + dp[i][j - 1];
    }
return dp[n][m];

题目2

将一个正整数拆分为成 2 的幂的和，例如：

7=1+2+4

7=1+2+2+2

7=1+1+1+4

7=1+1+1+2+2

7=1+1+1+1+1+2

7=1+1+1+1+1+1+1

总共有六种不同的拆分方案。

再比如：4 可以拆分成：4=4，4=1+1+1+1，4=2+2，4=1+1+2。

函数 f(n) 表示 n 的不同拆分的方案数，例如 f(7)=6。

请编写程序，读入一个正整数 n (1≤n≤1000000)，输出 f(n)

代码：

#include <cstring>
#include <iostream>
using namespace std;
int t, n;
int dp[1000011];
int main() {
          
   
    cin >> t;
    memset(dp, 0, sizeof(dp));
    dp[0] = 1, dp[1] = 1, dp[2] = 2;
    for (int i = 3; i <= 1000000; i++) {
          
   
        if (i % 2)
            dp[i] = dp[i - 1];
        else
            dp[i] = (dp[i - 1] + dp[i / 2]) % 1000000000;
    }
    for (int k = 0; k < t; k++) {
          
   
        cin >> n;
        cout << "case #" << k << ":
" << dp[n] << endl;
    }
    return 0;
}