数的划分,记忆化DFS,WA求调
查看原帖
数的划分,记忆化DFS,WA求调
1051584
Crushxl楼主2024/5/10 13:49
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 500;
long long f[MAXN][MAXN],vis[MAXN];
int N,K;

long long dfs(int n,int k,int last=1){
	if(k == K) return n==N?1:0;
	if(f[n][k] != -1) return f[n][k];
    long long sum = 0;
    for(int i=last;n+i<=N;i++){
    	sum += dfs(n+i,k+1,i);
	}
    f[n][k] = sum;
    return sum;
}

int main(){
	cin >> N >> K;
    memset(f,-1,sizeof(f));
    cout << dfs(0,0);
}
2024/5/10 13:49
加载中...