记忆化搜索

1500ms左右

C++ 代码

#include <iostream>
#include <cmath>
#include <cstring>

using namespace std;

const int N = 1010, mod = 1e9 + 7;

//记忆化搜索，memo[i, j]记录是当前和为i且上一个取的数为j的方案数
int memo[N][N];
int n;

int dfs(int sum, int pre){
    if(memo[sum][pre] > 0) return memo[sum][pre];
    if(sum == 0) return 1;  //搜索到一种方案，返回1
    int s = 0;
    for(int i = pre; i <= sum; i++){    //我们从nk开始划分，每次划分出来的数都不能小于前一个数
        s = (s + dfs(sum - i, i)) % mod;
        }
    return memo[sum][pre] = s;
}

int main(){
    scanf("%d", &n);
    int ans = dfs(n, 1);
    printf("%d\n", ans);
    return 0;
}

完全背包

$O(n^2)$

C++ 代码

#include <iostream>
#include <cmath>

using namespace std;

const int N = 1010, mod = 1e9 + 7;

int f[N];


//对于本题来说n1 = n, n2 = 2, ... , n3 = 1
//因此可以将问题转换为完全背包问题，每个ni都可以取无线限个，背包大小为n
//f[i, j]定义为在前i个数中取，和为j的方案数

int n;

int main(){
    scanf("%d", &n);
    int ans = 0;
    f[0] = 1;
    for(int i = 1; i <= n; i++){
        for(int j = i; j <= n; j++){
            f[j] = (f[j] + f[j - i]) % mod;
            }
        }
    printf("%d\n", f[n]);
    return 0;
}