AcWing
1050. 鸣人的影分身
两种做法。
dfs暴力，比较好想到。枚举每个数位(影分身)，同时要求每位数字只能递增(限制只有一种排列方式)，给出当前剩余的查克拉。如果查克拉不够当前数位的最小要求，则不满足条件；否则，如果数位是最后一位，那么方案数+1.
#include <bits/stdc++.h>
using namespace std;
int t, m, n;
int res;
void dfs(int digit, int mine, int delta){
if(mine > delta) return;
if(digit == n){
res ++;
return;
}
for(int i = mine; i <= delta; i ++) dfs(digit + 1, i, delta - i);
}
int main(){
cin >> t;
while(t --){
cin >> m >> n;
res = 0;
dfs(1, 0, m);
cout << res << '\n';
}
return 0;
}
dp：相当于是把n个苹果放m个盘子里的一道题。
#include<cstdio>
#include<algorithm>
#include<iostream>
using namespace std;
int f(int x,int y){
if(x == 0) return 1;//没有苹果，全部盘子为0
if(y == 0) return 0;//没有盘子，没法放
if(y > x){//盘子数大于苹果数，至多只能x个盘子上都放一个
return f(x,x);
}
return f(x - y, y) + f(x, y - 1);//盘子数小于等于苹果数 -> 分类讨论： 有盘子为空，没有盘子为空
//有盘子为空的时候即至少有一个盘子为空，f(x,y-1);没有盘子为空即最少每个盘子都有一个,f(x-y,y)
}
int main(){
int t,n,m;//n个苹果分到m个盘子里去，运行盘子为空
cin >> t;
while(t --){
cin >> n >> m;
cout << f(n,m) << endl;
}
return 0;
}
实际上可以发现，在递归的过程中要用到之前的数据，继而这道题可以转换为记忆化搜索，将结果保存来做，即dp做法。
#include <bits/stdc++.h>
using namespace std;
int t, m, n;
const int M = 15, N = 15;
int f[M][N];
int main(){
for(int i = 1; i <= 10; i ++) f[0][i] = 1;
for(int i = 1; i <= 10; i ++){
for(int j = 1; j <= 10; j ++){
f[i][j] = f[i][j - 1];
if(i >= j) f[i][j] += f[i - j][j];
}
}
cin >> t;
while(t --){
cin >> m >> n;
cout << f[m][n] << '\n';
}
return 0;
}