题解 | #放苹果#

//放苹果分为两种情况，一种是有盘子为空，一种是每个盘子上都有苹果。
// 令(m,n)表示将m个苹果放入n个盘子中的摆放方法总数。
// 1.假设有一个盘子为空，则(m,n)问题转化为将m个苹果放在n-1个盘子上，即求得(m,n-1)即可
// 2.假设所有盘子都装有苹果，则每个盘子上至少有一个苹果，即最多剩下m-n个苹果，问题转化为将m-n个苹果放到n个盘子上
// 即求(m-n，n)  dp[m][n] = dp[m][n-1] + dp[m-n][n](m>n) + dp[m][m](m<n)
let line;
while (line = readline()) {
    var [apples, plates] = line.split(' ');
    apples = parseInt(apples)
    plates = parseInt(plates)
    let dp = new Array(apples+1).fill(0).map(()=>new Array(plates+1).fill(0))
    
    for(let i=1;i<apples+1;i++){//一个盘子 只有一种放法
        dp[i][1] = 1;
    }
    for(let i=1;i<plates+1;i++){
        dp[0][i]=1      //0个苹果，一种放法
        dp[1][i]=1      //1个苹果，一种放法
    }
    
    const getCount = (m,n)=>{
        if(dp[m][n]>0)
            return dp[m][n]
        if(m<n){
            dp[m][n] = getCount(m,m)
            return dp[m][n];
        }
        if(m>=n){
            dp[m][n] = getCount(m,n-1) + getCount(m-n,n)
            return dp[m][n]
        }
    }
    
    console.log(getCount(apples,plates))
    
}