题解 | #放苹果#

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 a = parseInt(tokens[0]);
    //     let b = parseInt(tokens[1]);
    //     console.log(a + b);
    // }
    let line = await readline();
    const [m, n] = line.split(/\s+/).map((item) => {
        return +item;
    });
    // 排列组合  事件复杂度没有问题，空间复杂度过不了
    // // console.log(n,m)
    // const mL = new Array(m).fill(0);
    // const res = new Set();
    // const list = [];
    // function occ(i) {
    //     if (i == n) {
    //         list.push(mL.toString());
    //         return;
    //     }
    //     for (let j = 0; j < m; j++) {
    //         mL[j]++;
    //         occ(i + 1);
    //         mL[j]--;
    //     }
    // }
    // occ(0);
    // list.forEach((item) => {
    //    let temp= Array.from(item).sort();
    //     // console.log(temp.toString())
    //     if (!res.has(temp.toString())) {
    //         res.add(temp.toString());
    //     }
    // });

    // console.log(res.size);

    // m<n  至少有n-m个盘子空着,确定的  大问题转换成小问题  (m,n-m)
    // m>n 盘子不空 (m-n,n)   盘子有空的 （m,n-1)
    // 定义 fn(m,n-1) 是 把m个苹果放到最多n个盘子里去  
    //  m==1  return 1 n==1 return 1 
    function occ2(m,n){
        if(m==0||m==1||n==1||n==0){
            return 1
        }
        if(m<n){
            return occ2(m,m)
        }else{
            return occ2(m-n,n)+occ2(m,n-1)
        }
    }
    let res=occ2(m,n)
    console.log(res)
})();