域名更换网站,陶瓷刀具网站策划书,精准广告投放,今天邯郸下的紧急通知给定不同面额的硬币和一个总金额。写出函数来计算可以凑成总金额的硬币组合数。假设每一种面额的硬币有无限个。
示例 1:
输入: amount 5, coins [1, 2, 5] 输出: 4 解释: 有四种方式可以凑成总金额: 55 5221 52111 511111 示例 2:
输入: amount 3, coins [2] 输出: 0 解… 给定不同面额的硬币和一个总金额。写出函数来计算可以凑成总金额的硬币组合数。假设每一种面额的硬币有无限个。
示例 1:
输入: amount 5, coins [1, 2, 5] 输出: 4 解释: 有四种方式可以凑成总金额: 55 5221 52111 511111 示例 2:
输入: amount 3, coins [2] 输出: 0 解释: 只用面额2的硬币不能凑成总金额3。 示例 3:
输入: amount 10, coins [10] 输出: 1
注意:
你可以假设
0 amount (总金额) 50001 coin (硬币面额) 5000硬币种类不超过 500 种结果符合 32 位符号整数
解题思路
数组定义
dp[i]代表金额为i时的组合数
状态转移
遍历所有金额的情况当前金额i可能由金额i-coin的情况转移而来
dp[i]dp[i-coin];
因为最外层循环遍历了所有硬币所以可以排除了重复的组合数
代码
class Solution {public int change(int amount, int[] coins) {int[] dp new int[amount 1];dp[0]1;for (int coin : coins) {for (int icoin;iamount;i){dp[i]dp[i-coin];}}return dp[amount];}
}
