放苹果-详解+BUG
放苹果
http://www.nowcoder.com/questionTerminal/4f0c1e21010e4d849bde5297148e81d9
思路
设f(m, n)表示将m个苹果放到n个盘子中的方法数
把问题分成两种情况
- 盘子数n > 苹果数m ：则无论怎样放必然有n - m个空盘子，这些盘子都废掉了。实际上f(m , n) = f(m , m)
- 盘子数n <= 苹果数m: 这时候考虑到底是每个盘子都放苹果还是留至少一个空盘子。若都放，则先每个盘子都预置一个苹果，还剩m-n个苹果放到n个盘子，即f(m-n, n)；若留空盘子，至少留一个，则将m个苹果放到n-1个盘子中,即f(m , n-1) 。故而f(m,n) = f(m-n, n) + f(m , n-1)；
边界情况
- n = 1时， 只有一个盘子了，显然只能把所有的苹果都放在里面
- m = 0时， 没有苹果了，那就不放了，不放本身也是一种方法。(实际上是考虑到f(m-n, n)，若m=0时设置值为0,则当n = m时,不留空盘子策略f(m-n, n) = 0，这就不对了)
爆搜 记忆化搜索 dp都可以解决该问题
- BUG
- 此题样例错误，容易让人认为先输入测试组数t，故而按照样例格式输入时能通过自测样例，在提交代码时会出现答案错误或者段错误。
- AC CODE
#include<bits/stdc++.h>
using namespace std;
int dp[20][20];
//m个苹果放在n个盘子里
int dfs(int m, int n) {
if (n == 1) return 1;
if (m == 0) return 1;
if (dp[m][n] != -1) return dp[m][n];
if (m < n) {
return dp[m][n] = dfs(m, m);
}
else {
return dp[m][n] = dfs(m - n, n) + dfs(m, n - 1);
}
}
int main() {
int m, n, t;
memset(dp, -1, sizeof dp);
while (cin >> m >> n) {
int k = dfs(m, n);
cout << k << endl;
}
}
