题解 | 放苹果

看了大佬们的题解，对于递归的解释我没法一下看懂，后来自己动手写写再梳理了下，希望下面的能让后面的人一下子理解到。

（动态规划法好绕啊……看不懂，还是递归好理解一点……虽然对我来说还是有点难以理解。）

题析1：相同的盘子 -> 摆放顺序不影响方案数

1. m < n：苹果数量小于盘子数量，方案数取决于苹果数量，至多有n-m个盘子空着，空的盘子不影响方案数。最多占用m个盘子，转化为m个苹果摆放在m个盘子中的问题。
2. m >= n：苹果数量大于等于盘子数量。分两种情况：
1. 至少有一个盘子空着，所以问题转化为m个苹果放到n-1个盘子的问题；
1. 空2个乃至更多盘子，可以通过递归逐级转化为n-1个盘子的问题。
2. 相当于递归到最后一层，通过n-1和m-n的操作，就逐级转化成了要么只剩一个盘子（1种方案），要么就只剩1个苹果（1种方案）。
2. 所有盘子都有苹果，每个盘子至少有一个苹果，所以问题转化为m-n个苹果放到n个盘子的问题；

每次递归，都要考虑1和2两种情况。

const rl = require("readline").createInterface({ input: process.stdin });
var iter = rl[Symbol.asyncIterator]();
const readline = async () => (await iter.next()).value;

void async function () {
    // Write your code here
    while(line = await readline()){
        let tokens = line.split(' ');
        let m = parseInt(tokens[0]); // 苹果
        let n = parseInt(tokens[1]); // 盘子

        /**
         * 题析1：相同的盘子 -> 摆放顺序不影响方案数
         * 
         * m < n:
         * 苹果数量小于盘子数量，方案数取决于苹果数量，至多有n-m个盘子空着，空的盘子不影响方案数。
         * 最多占用m个盘子，转化为m个苹果摆放在m个盘子中的问题。
         * 
         * m >= n:
         * 苹果数量大于等于盘子数量。分两种情况：
         * 1. 至少有一个盘子空着，所以问题转化为m个苹果放到n-1个盘子的问题；
         *  1.1 空2个乃至更多盘子，可以通过递归逐级转化为n-1个盘子的问题。
         *  1.2 相当于递归到最后一层，通过n-1和m-n的操作，就逐级转化成了要么只剩一个盘子（1种方案），要么就只剩1个苹果（1种方案）。
         * 2. 所有盘子都有苹果，每个盘子至少有一个苹果，所以问题转化为m-n个苹果放到n个盘子的问题；
         * 
         * 每次递归，都要考虑1和2两种情况。
         */

        let res = 1

        function recursion(m, n) {
            if (n === 1 || m === 1 || m === 0) { // 只有一个盘子/只有一个苹果/没有苹果
                return res = 1
            } else if (m < n) {
                return recursion(m, m)
            } else if (m >= n) {
                return recursion(m, n - 1) + recursion(m-n, n)
            }
        }
        recursion(m, n)
        console.log(recursion(m, n));
    }
}()