算法题：数的划分，用记忆化DFS做WA求调

Question

题意简述

把数n划分成k个互不相同的正整数，不同顺序方案算同一种，求总共的方案数量。

代码

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 2022;
const int MAXK = 10;
long long f[MAXN+5][MAXK+5];

long long dfs(int n,int k,int last){    //n：累加的数，k：划分次数，last：上次划分出的数 
    if(k == MAXK) return n==MAXN?1:0;
    if(f[n][k] != -1) return f[n][k];
    long long sum = 0;
    for(int i=last;n+i<=MAXN;i++){
        sum += dfs(n+i,k+1,i+1);
    }
    f[n][k] = sum;
    return sum;
}

int main(){
    memset(f,-1,sizeof(f));
    cout << dfs(0,0,1);
    return 0;
}

上面代码输出的答案少了，求调，要用记忆化的DFS，感谢！！

Answer 1

使用动态规划，记录已计算过的子问题结果。

以上回复有部分引自免费微信小程序：皆我百晓生。 如问题尚未解决，还请稍待，如有疑问请回复进一步沟通。