题解 | #放苹果#
放苹果
http://www.nowcoder.com/practice/bfd8234bb5e84be0b493656e390bdebf
#include"iostream" #include"algorithm" #include"cstring" #include"vector" #include"map" #include"set" #include"cmath" using namespace std;
/* 典型的动态规划的题解：f(m,n) 表示 m个苹果放到n个盘子里面的总可能数；
1、当至少有一个空盘子时：f(m,n) = f(m,n-1); // 在递归的调用过程中会调用到f(m,n-k) k = 2,3,4...
2.当所有盘子都有苹果时：f(m,n) = f(m-n,n);
因此最终的最次数应是f(m,n) = f(m-n,n) + f(m,n-1);
*/
const int MAX = 12;
int dp[MAX][MAX];
// 动态规划做法；
int main()
{
int n , m ;
while(cin>>m>>n) //m表示苹果，n表示盘子；
{
memset(dp,0,sizeof(dp)); // 头函数是 cstring
for(int i = 0 ; i <= m ;i++ )
dp[i][1] = 1; // 当只有一个盘子时，只有一种摆法；
for(int j = 0 ; j <= n ; j++)
dp[0][j] = 1 ;//dp[1][j] = 1; // 当没有苹果或者只有一个苹果时，只有一种摆法；
for(int i = 1; i <= m ;i++ )
{
for(int j = 1 ; j <= n ; j++)
if(i < j) // 当苹果数小于盘子数时，j-i个盘子必然时空的，所以在i个盘子里面放i个苹果；
dp[i][j] = dp[i][i];
else
dp[i][j] = dp[i-j][j]+dp[i][j-1];
}
cout<<dp[m][n]<<endl;
}
return 0;
}
/* 递归做法：DFS;
int f(int m, int n) { if(m < 0) // 当没有苹果时，也算是一种摆法； return 0; if(m == 1 || n == 1) return 1; return f(m-n,n) + f(m,n-1); // f(m,n-1)的递归调用过程中会调用到f(m,n-k) k = 2,3,4... }
int main() { int n , m ; while(cin>>m>>n) { cout<<f(m,n)<<endl; }
return 0;
} */