518. 零钱兑换 II - 力扣（LeetCode）

class Solution {
    public int change(int amount, int[] coins) {
        // 创建dp数组,dp[i][j] 表示使用前i个硬币（下标为0的硬币是前1个）凑成总金额j的硬币组合数
        int[][] dp = new int[coins.length + 1][amount + 1];
        // 没有银币情况下凑成总金额j(J>0)的组合一定为0;
        for (int j = 1; j <= amount; j++) {
            dp[0][j] = 0;
        }

        // 选前i个银币的情况下，存在凑成总和为0的方案数量为 1
        for (int i = 0; i <= coins.length; i++) {
            dp[i][0] = 1;
        }

        for (int i = 1; i <= coins.length; i++) { // 依次处理银币
            int val = coins[i - 1]; // 当前这个银币的价值

            for (int j = 0; j <= amount; j++) {
                // 不选择当前这个硬币，凑成总金额j的硬币组合数
                dp[i][j] = dp[i - 1][j];

                // 多次选择当前银币
                for (int k = 1; k * val <= j; k++) {
                    dp[i][j] += dp[i - 1][j - k * val];
                }
            }
        }

        // for(int i=0;i<=coins.length;i++){
        // for(int j=0;j<=amount;j++){
        // System.out.printf("%3d",dp[i][j]);
        // }
        // System.out.println("\n");
        // }
        return dp[coins.length][amount];
    }
}

 

class Solution {
    public int change(int amount, int[] coins) {
        // 创建dp数组,dp[i][j] 表示使用前i个硬币（下标为0的硬币是前1个）凑成总金额j的硬币组合数
        int[] dp = new int[amount + 1];
        dp[0] = 1;

        for (int i = 1; i <= coins.length; i++) { // 依次处理银币
            int val = coins[i - 1]; // 当前这个银币的价值
            for (int j = val; j <= amount; j++) {
                // 不选择当前这个硬币，凑成总金额j的硬币组合数
                dp[j] = dp[j];
                // 多次选择当前银币
                dp[j] += dp[j - val];
            }
        }

        return dp[amount];
    }
}

LCR 103. 零钱兑换 - 力扣（LeetCode）

class Solution {
    public int coinChange(int[] coins, int amount) {
        int[] dp = new int[amount + 1];
        Arrays.fill(dp, 1001);

        dp[0] = 0;
        for (int i = 0; i < coins.length; i++) {
            if (coins[i] <= amount) {
                dp[coins[i]] = 1;
            }
        }

        // for (int i = 1; i <= amount; i++) {
        //     for (int j = 1; j <= i / 2; j++) {
        //         if(dp[j] == 1001 || dp[i - j] == 1001){
        //             continue;
        //         }

        //         if(dp[i - j] + dp[j] < dp[i]){
        //             dp[i] = dp[i - j] + dp[j];
        //         }
        //     }
        // }

        // return dp[amount] != 1001 ? dp[amount] : -1;

        for(int i=1;i<=amount;i++){
            for(int j=0;j<coins.length;j++){
                if(i > coins[j]){
                    dp[i] = Math.min(dp[i-coins[j]]+1,dp[i]);
                }
            }
        }

        return dp[amount] != 1001 ? dp[amount] : -1;

    }
}

377. 组合总和 Ⅳ - 力扣（LeetCode）

class Solution {
    public int combinationSum4(int[] nums, int target) {
        int[] dp = new int[target+1];
        dp[0] = 0;
        
        for(int i=0;i<nums.length;i++){
            if(nums[i] <= target){
                dp[nums[i]] = 1;
            }
        }
        
        for(int j=1;j<=target;j++){
            for(int i=0;i<nums.length;i++){
                if(j>nums[i]){
                    dp[j] += dp[j-nums[i]];
                }
            }
        }
        
        return dp[target];
    }
}