火炬开发区网站建设,外贸平台有哪些是免费的,谈谈你对企业网站的页面设计,设计上海展会2021门票入门题目 把m个同样的苹果放在n个同样的盘子里#xff0c;允许有的盘子空着不放#xff0c;问共有多少种不同的分法#xff1f;注意#xff1a;如果有7个苹果和3个盘子#xff0c;#xff08;5#xff0c;1#xff0c;1#xff09;和#xff08;1#xff0c;5#…入门题目 把m个同样的苹果放在n个同样的盘子里允许有的盘子空着不放问共有多少种不同的分法注意如果有7个苹果和3个盘子511和151被视为是同一种分法。示例1输入 7 3输出 81 明确子问题是什么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 初始值1111001001001001001001003 子问题的递推关系 if m n : # 苹果数量少于盘子数量 100 个苹果放在 5 个盘子的放法数量和 5个苹果放在5个盘子的放法数量一样dp[m][n] dp[m][m]else mn :# 所有的盘子都不空的情况 存在一个盘子空的情况dp[m][n] dp[m-n][n] dp[m][n-1] 4 确定DP数组的计算顺序递推 defdfs(m,n) :ifm0 :return1 ; ifn1 :return1 ; # 只有一个盘子就只有一个放法 ifmn : returndfs(m,m)# 没有空盘子的放法(每个盘子都至少一个苹果) 至少一个盘子空着的方法returndfs(m-n, n) dfs(m, n-1)if__name____main__ :m,nmap(int,(input().split()) )resdfs(m,n)print(res) 动态规划 # import numpy as np defdfs(m,n) :ifm0 :return1 ; ifn1 :return1 ; # 只有一个盘子就只有一个放法 ifmn : returndfs(m,m)# 没有空盘子的放法 至少一个盘子空着的方法returndfs(m-n, n) dfs(m, n-1)if__name____main__ :m,nmap(int,(input().split()) )# res dfs(m,n)# print(res)# dp np.zeros([m1,n1],dtypeint)dp [[0foriinrange(n1)] foriinrange(m1)]# 初始化foriinrange(1,n1): dp[0][i] 1 ; forjinrange(1,m1): dp[j][1] 1 ; foriinrange(1,m1) :forjinrange(1,n1) : # 如果苹果数量少于盘子ifij : 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])
