HJ61 放苹果

题目描述

示例

代码

动态规划

/*
说是一道动态规划的题
动态规划的核心就是找出口，并将问题转化，大问题转小问题，递归的思想

放苹果分为两种情况，一种是有盘子为空，一种是每个盘子上都有苹果。
令(m,n)表示将m个苹果放入n个盘子中的摆放方法总数。
1.假设有一个盘子为空，则(m,n)问题转化为将m个苹果放在n-1个盘子上，即求得(m,n-1)即可
2.假设所有盘子都装有苹果，则每个盘子上至少有一个苹果，即最多剩下m-n个苹果，问题转化为将m-n个苹果放到n个盘子上
即求(m-n，n)
*/

let readline = require('readline')
let rl = readline.createInterface({
    input: process.stdin,
    output: process.stdout
})

rl.on('line', line=>{
    let [m, n] = line.split(' ')
    let count = dp(m, n)
    
    console.log(count)
})

// m 表示 苹果
// n 表示 盘子
function dp(m, n){
    // 出口，
    if(m<0 || n<=0){ // m-n可能小于0，所以判断m<0
        return 0
    }
    if(m==1 || n==1 || m==0){ // 额外增加的m=0，是为了满足满足题意，就是凑出口
        return 1
    }
    /*
        令(m,n)表示将m个苹果放入n个盘子中的摆放方法总数。
        1.假设有一个盘子为空，则(m,n)问题转化为将m个苹果放在n-1个盘子上，即求得(m,n-1)即可
        2.假设所有盘子都装有苹果，则每个盘子上至少有一个苹果，即最多剩下m-n个苹果，问题转化为将m-n个苹果放到n个盘子上
        即求(m-n，n)
     */
    return dp(m ,n-1) + dp(m-n, n)
}

题目来源

HJ61 放苹果