✨今日算法一题
文章目录
零钱兑换||
题目描述
思路详解
本题用了完全背包的思想。
我们利用双重循环，进行对金额的判断。进行累计。
详细见代码注释。
代码与结果
class Solution { // 组合数 public int change(int amount, int[] coins) { Arrays.sort(coins); // 这里取 amount + 1, 是因为要含 dp[0],即金额为0 int[] dp = new int[amount + 1]; // 注意初始值为1，而不是0 dp[0] = 1; // 硬币面值作为外循环 for (int coin : coins) { // 金额作为内循环，且保证组合不重复 // 这里i从coin开始的原因是：当 i < coin时，没有硬币满足要求。 for (int i = coin; i <= amount; i++) { // i - coin 表示剩余的金额 // 使用dp[i - coin]可以利用之前的计算结果 // 注意每个dp[i], i>0，初始值均为0 dp[i] = dp[i] + dp[i - coin]; } } return dp[amount]; } }
