放苹果

Posted on Edited on In ,

描述

放苹果_牛客题霸_牛客网
把m个同样的苹果放在n个同样的盘子里，允许有的盘子空着不放，问共有多少种不同的分法？
注意：如果有7个苹果和3个盘子，（5，1，1）和（1，5，1）被视为是同一种分法。
数据范围：0 <= m <= 10 ，1 <= n <= 10

输入描述：

输入两个int整数

输出描述：

输出结果，int型

示例1

输入：
7 3

输出：
8

思路：减少盘子， 或者减少苹果，让情况退化
可以分为一下两种情况：
盘子 > 苹果
当盘子的数量比苹果多的时候，把多余的盘子拿走不会对结果产生影响
盘子 <= 苹果
当盘子的数量比苹果多的时候，又可以分为两种情况
一种情况是盘子上全放了苹果
如果都放了苹果则所有的盘子上都拿去一个苹果对结果不会产生影响
另一种情况是有的盘子上没放苹果
既然有点盘子没有放苹果, 那么拿走一个空盘也不会对结果产生影响

解1 递归

1
2
3
4
5
6
7
8
// const [m, n] = readline().split(' ').map(Number);
function sol(m, n){
//   console.log('mn',m,n)
  if(m <= 1 || n <= 1) return 1;
  if(n > m) return sol(m ,m);
  return sol(m, n - 1) + sol(m - n, n);
}
console.log(sol(3, 3))

解2 动态规划

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
function putApple(m, n){
  const arr = new Array(m + 1);
  for(let i = 0; i < m + 1; i++){
    arr[i] = new Array(n + 1).fill(1)
  }
  // console.log(arr)
  for(let i = 1; i < m + 1; i++){
    for(let j = 1; j < n + 1; j++){
      if(i <= 1 || j <= 1){
        arr[i][j] = 1;
        continue;
      }
      if(i < j){
        arr[i][j] = arr[i][i];
        continue;
      }
      arr[i][j] = arr[i - j][j] + arr[i][j - 1]
      
    }
  }

  console.log(arr.join('\n'))
  return arr[m][n];
}

putApple(3,3)