3428. 放苹果
DFS
#include <iostream>
using namespace std;
int m, n, res;
void dfs(int u, int sum, int last){
if(u == n){
if(sum == 0){
res ++;
return;
}
return;
}
for(int i=last; i<=sum; i++) dfs(u+1, sum-i, i);
}
int main(){
while(cin>>m>>n){
res = 0;
dfs(0, m, 0);
cout<<res<<endl;
}
return 0;
}
DP
#include <iostream>
#include <cstring>
using namespace std;
int t, m, n;
int dp[15][15];
int main(){
while(cin>>m>>n){
memset(dp,0,sizeof dp);
dp[0][0] = 1;
for(int i=0; i<=m; i++){
for(int j=1; j<=n; j++){
//f[i][j-1]表示能量为i,j-1个数的和为i的方案数
dp[i][j] = dp[i][j-1];
//f[i-j][j]表示能量为i-j,j个数的和为i-j的方案数
if(i>=j) dp[i][j] += dp[i-j][j];
}
}
cout<<dp[m][n]<<endl;
}
}