题解 | #放苹果#

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

// 递归写法：
/*
  递归退出条件：
  苹果数只有1个，放哪个盘子都一样，方案为1
  苹果数为0，放置已经完成，方案为1
  盘子数为1，则手上的所有苹果都会放在这一个盘子中，方案为1
*/
// 如果盘子数大于苹果树：则必定有n-m个盘子空着，不会影响总的方案书，所以f(m,n)等价于f(m,m)
/*
  如果盘子数小于等于苹果数：则考虑是不是放满所有盘子。如果至少空一个盘子，则有f(m,n-1)；如果不要空盘子，则每个盘子至少放了一个苹果，放了不会影响方案总数，因此有f(m-n,n)个方案
*/

/*function solution(m,n){
  if(m === 0 || m === 1 || n === 1){
    return 1
  }else if(n > m){
    return solution(m,m)
  }else{
    return solution(m,n-1) + solution(m-n,n)
  }
}

rl.on('line',function(line){
  const arr = line.split(' ').map(item => +item)
  const res = solution(arr[0],arr[1])
  console.log(res)
})*/



/*
  动态规划：处理边缘节点（苹果数只有1个，放哪个盘子都一样，方案为1
  苹果数为0，放置已经完成，方案为1
  盘子数为1，则手上的所有苹果都会放在这一个盘子中，方案为1）
*/
// dp[i][j] 表示对于i个苹果和j个盘子有多少种放置方案
/*
* 两种情况：
* 当 i < j 时，苹果数量比盘子数量少，盘子一定会空，因此当前状态转移方程为 dp[i][j] = dp[i][i]；
* 当 i >= j 时，苹果数量多于盘子，则考虑是不是每个盘子都装苹果，如果不装满盘子，至少有一个盘子不装，方案有 dp[i][j-1]；如果装满盘子，每个盘子中至少有一个苹果，
* 相当于都去掉一个苹果后再分配，方案有 dp[i-j][j]。因此状态转移方程为 dp[i][j] = dp[i-j][j] + dp[i][j-1]
*
* 综上：状态转移方程为 dp[i][j] = {
*   dp[i][i]    if(i<j)
*   dp[i-j][j] + dp[i][j-1]  if(i>=j)
*  }
* */

function solution(m,n){
  // j为0代表1个盘子，i为0代表0个苹果，i为1代表1个苹果（因为题目规定苹果可以为0，盘子最少是1）
  // 这里的j长度为n，i苹果数是加上了1的基础，j就是从0到n-1，所以在进行i、j代换时，需要有一个1的差值，不是很方便后续表达式代换
  const dp = new Array(m+1).fill(0).map(item => [])
  for(let j=0;j<n;j++){
    dp[0][j] = 1
    dp[1][j] = 1
  }
  for(let i=0;i<m+1;i++){
    dp[i][0] = 1
  }
  for(let i=2;i<m+1;i++){
    for(let j=1;j<n;j++){
      if(i < j+1){
        dp[i][j] = dp[i][i-1]
      }else{
        dp[i][j] = dp[i-j-1][j] + dp[i][j-1]
      }
    }
  }
//   console.log(dp)
  console.log(dp[m][n-1])
}

/*
function solution(m,n){
  // j为1代表1个盘子，i为0代表0个苹果，i为1代表1个苹果。
  // 这里定义的j的长度为n+1，是与i苹果的数目一样在基础上加了1的，方便后面的表达式书写
  const dp = new Array(m+1).fill(0).map(item => [])
  for(let j=1;j<n+1;j++){
    dp[0][j] = 1
    dp[1][j] = 1
  }
  for(let i=0;i<m+1;i++){
    dp[i][1] = 1
  }
  for(let i=2;i<m+1;i++){
    for(let j=2;j<n+1;j++){
      if(i < j){
        dp[i][j] = dp[i][i]
      }else{
        dp[i][j] = dp[i-j][j] + dp[i][j-1]
      }
    }
  }
  // console.log(dp)
  console.log(dp[m][n])
}
*/


rl.on('line',function(line){
  const arr = line.split(' ').map(item => +item)
  solution(arr[0],arr[1])
})