• 周四. 8月 11th, 2022

5G编程聚合网

5G时代下一个聚合的编程学习网

热门标签

动态规划求组合数和排列数的区别

admin

11月 28, 2021
爬楼梯问题:
实际是求排列数即:对于爬上3层,先2后1和先1后二是两种不同的方法。
状态定义:dp[i] 表示到达第i层的方法有多少种。
状态转移:dp[i] = dp[i – 1] + dp[i- 2];
 
零钱兑换问题:
实际是组合数问题即:要凑3块钱,先选择2块还是先选择1块的零钱都只算1种方法。
子问题定义:对于硬币从0到k,必须使用第k个硬币时当前金额的组合数。
状态定义:dp[i]表示对于选择第k个硬币时凑到金额i的组合数。
状态转移:dp[i] = dp[i] + dp[i – coin[k]];
关键:因为外循环时先遍历硬币种类数,所以其实这里规定了硬币的顺序,即排除了同样组合硬币的其他排列方式。

发表评论

您的电子邮箱地址不会被公开。