[数据结构与算法]leetcode 322. 零钱兑换（java）

学习完完全背包 练习

我好笨啊啊啊

二维?

class Solution {
    int INF = 1000000000;
    public int coinChange(int[] coins, int amount) {
        int n = coins.length;
        int[][] dp = new int[n + 1][amount + 1];

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

        return dp[n][amount] == INF ? -1 : dp[n][amount]; 
    }
}

一维

class Solution {
    public int coinChange(int[] coins, int amount) {
        int n = coins.length;
        int[] dp =new int[amount + 1];
        Arrays.fill(dp, amount + 1);
        dp[0] = 0;
        for(int i = 1; i <= amount; i ++){
            for(int j = 0; j < n; j ++){
                if(coins[j] <= i){
                    dp[i] = Math.min(dp[i], dp[i - coins[j]] + 1);
                }
            }
        }
        return dp[amount] > amount ? -1 : dp[amount];
    }
}

创作打卡挑战赛

赢取流量/现金/CSDN周边激励大奖