admin管理员组

文章数量:1026989

零钱兑换问题c语言编程,leetcode

这是完全背包问题，其中背包的容量就是 amount， 物品就是硬币，其中物品的数量是无限个的，而物品的重量，这里就是硬币的价值。因此  dp[i][j]  表示的是 前i个硬币可以凑成价值为 j 的钱数 的总的方法数。状态转移方程就是 dp[i][j] = dp[i-1][j] + dp[i][j - coins[i-1]] ，

dp[i-1][j] 表示：(不用这第i个硬币)只用 前 i-1 中硬币就可以凑出价值为 j 的总数，

dp[i][j- coins[i-1]]表示 ： 要用这第i个硬币，那么就要关注如何凑出价值 j-coins[i-1]这个钱数的方法。

题目

code

注意：1.区分状态转移方程：dp[i][j] = dp[i - 1][j] + dp[i-1][j - nums[i - 1]]; 和

dp[i][j] = dp[i - 1][j] + dp[i][j - nums[i - 1]];

这里面的零钱可以重复选择，所以选了这个零钱之后，dp[i][j] = dp[i][j- nums[i-1]]

如果不可以重读选择 就是 dp[i][j] = dp[i - 1][j] + dp[i-1][j - nums[i - 1]]

2.j有时候要从0开始

3.降维的时候，j要倒着算，从j = sum开始减

零钱兑换问题c语言编程,leetcode

这是完全背包问题，其中背包的容量就是 amount， 物品就是硬币，其中物品的数量是无限个的，而物品的重量，这里就是硬币的价值。因此  dp[i][j]  表示的是 前i个硬币可以凑成价值为 j 的钱数 的总的方法数。状态转移方程就是 dp[i][j] = dp[i-1][j] + dp[i][j - coins[i-1]] ，

dp[i-1][j] 表示：(不用这第i个硬币)只用 前 i-1 中硬币就可以凑出价值为 j 的总数，

dp[i][j- coins[i-1]]表示 ： 要用这第i个硬币，那么就要关注如何凑出价值 j-coins[i-1]这个钱数的方法。

题目

code

注意：1.区分状态转移方程：dp[i][j] = dp[i - 1][j] + dp[i-1][j - nums[i - 1]]; 和

dp[i][j] = dp[i - 1][j] + dp[i][j - nums[i - 1]];

这里面的零钱可以重复选择，所以选了这个零钱之后，dp[i][j] = dp[i][j- nums[i-1]]

如果不可以重读选择 就是 dp[i][j] = dp[i - 1][j] + dp[i-1][j - nums[i - 1]]

2.j有时候要从0开始

3.降维的时候，j要倒着算，从j = sum开始减

本文标签： 零钱兑换问题c语言编程LeetCode

版权声明：本文标题：零钱兑换问题c语言编程,leetcode 内容由热心网友自发贡献，该文观点仅代表作者本人， 转载请联系作者并注明出处：http://it.en369.cn/IT/1688198449a190998.html， 本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌抄袭侵权/违法违规的内容，一经查实，本站将立刻删除。