放苹果-详解+BUG

• 思路

  • 设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;
    }
}