放苹果HJ61

入门题目

把m个同样的苹果放在n个同样的盘子里，允许有的盘子空着不放，问共有多少种不同的分法？
注意：如果有7个苹果和3个盘子，（5，1，1）和（1，5，1）被视为是同一种分法。

示例1

输入：

7 3

输出：

8

1 明确子问题是什么？

m个苹果,n个盘子，他们之间存在的关系要么 m 大于 n , m等于 n，或者 m 小于n ;

所有盘子都放苹果的对立事件是什么？
所有盘子都放苹果的对立事件是至少有一个盘子没有放置苹果。因为在所有的盘子都放置了苹果的情况下，没有盘子是没有放置苹果的，所以所有盘子都放苹果和至少有一个盘子没有放置苹果是互为对立事件。换句话说，如果一个事件发生了，那么另一个事件一定不会发生。

我们定义 dp[ m] [n] 为，m个苹果 ，n个盘子时，一共的分法。就是有两种放苹果的情况，要么n个盘子都放满，要么至少空一个盘子。

dp[ m] [n] = n个盘子都放满的放法 + 至少空一个盘子的方法

n个盘子都放满的方法 ： 即要保证所有的盘子中至少都有一个，其他的随便放，所以每个盘子都减去一个苹果，共减去n个苹果即m-n 个，即变成了 m-n 个苹果放在n 个盘子中的放法 ,dp[m-n] [n] 。

至少空一个盘子的方法 ：dp[m] [n-1]

保证子问题之间互斥，不重叠。

2 初始值

3 子问题的递推关系

 if m< n : # 苹果数量少于盘子数量  100 个苹果放在 5 个盘子的放法数量和 5个苹果放在5个盘子的放法数量一样dp[m][n] = dp[m][m]else m>n :# 所有的盘子都不空的情况 + 存在一个盘子空的情况dp[m][n] = dp[m-n][n] + dp[m][n-1] 

4 确定DP数组的计算顺序

递推

 ​defdfs(m,n) :ifm==0 :return1 ; ifn==1 :return1 ; # 只有一个盘子就只有一个放法 ​​ifm<n : returndfs(m,m)# 没有空盘子的放法(每个盘子都至少一个苹果) + 至少一个盘子空着的方法returndfs(m-n, n) +dfs(m, n-1)​if__name__=='__main__' :m,n=map(int,(input().split()) )res=dfs(m,n)print(res)    

动态规划

 # import numpy as np ​defdfs(m,n) :ifm==0 :return1 ; ifn==1 :return1 ; # 只有一个盘子就只有一个放法 ​​ifm<n : returndfs(m,m)# 没有空盘子的放法 + 至少一个盘子空着的方法returndfs(m-n, n) +dfs(m, n-1)​if__name__=='__main__' :m,n=map(int,(input().split()) )# res = dfs(m,n)# print(res)# dp = np.zeros([m+1,n+1],dtype=int)dp= [[0foriinrange(n+1)] foriinrange(m+1)]# 初始化foriinrange(1,n+1): dp[0][i] =1 ; forjinrange(1,m+1): dp[j][1] =1 ; ​foriinrange(1,m+1) :forjinrange(1,n+1) : # 如果苹果数量少于盘子ifi<j  : dp[i][j] =dp[i][j-1]else :# dp[i][j] 即每个状态# dp[i][j] =dp[i-j][j] +dp[i][j-1]​print(dp[m][n])​ ​