322. 零錢(qián)兌換

動(dòng)態(tài)規(guī)劃-自頂向下

• 定義 要湊出金額n 至少要dp(coins,n)個(gè)硬幣
• 確定base case 目標(biāo)金額為0 返回0
• 確定 狀態(tài) 也就是原問(wèn)題和子問(wèn)題中的變量，你每次抽取一個(gè)硬幣，都會(huì)導(dǎo)致目標(biāo)金額減少，所以狀態(tài)就是目標(biāo)金額
• 確定選擇，也就是導(dǎo)致?tīng)顟B(tài)產(chǎn)生變化的行為，每次選一個(gè)硬幣都會(huì)導(dǎo)致目標(biāo)金額的減少
• 明確dp數(shù)組的定義，狀態(tài)數(shù)組的每一個(gè)值都是代表目標(biāo)金額

class Solution {
    int[] memo;
    public int coinChange(int[] coins, int amount) {
        // 創(chuàng)建子問(wèn)題狀態(tài)數(shù)組
        memo = new int[amount + 1];

        Arrays.fill(memo,-666);// 初始化一個(gè)特殊值 表示還沒(méi)有計(jì)算

        // 題目要求的最終結(jié)果就是dp
        return dp(coins,amount);
    }

    // 定義 要湊出金額n 至少要dp(coins,n)個(gè)硬幣
    // dp狀態(tài)是  變化的 也就是原問(wèn)題和子問(wèn)題的變量  由于硬幣數(shù)量無(wú)限，仔細(xì)想一下  你每次抽取一個(gè)硬幣 變化的是什么 目標(biāo)總金額  抽取硬幣的次數(shù)就是狀態(tài)數(shù)組的長(zhǎng)度  每次抽取 狀態(tài)變量都會(huì)變化
    int dp(int[] coins,int amount){
        // base case
        if(amount == 0){
            return 0;
        }

        if(amount < 0){
            return -1;
        }

        if(memo[amount] != -666){
            return memo[amount];// 查找子問(wèn)題的解
        }

        int res = Integer.MAX_VALUE;
        for(int coin: coins){
            // 拿走一個(gè)硬幣 計(jì)算子問(wèn)題的解
            int sub  = dp(coins,amount - coin);

            // 子問(wèn)題無(wú)解 就跳過(guò)
            if(sub == -1){
                continue;
            }

            // 更新解  因?yàn)樾枰钌倌米哂矌诺拇螖?shù)
            res = Math.min(res,sub + 1);
        }


        // 將計(jì)算結(jié)果存入 子問(wèn)題數(shù)組
        memo[amount] = (res == Integer.MAX_VALUE) ? -1:res;
        return res == Integer.MAX_VALUE ? -1:res;
    }
}

動(dòng)態(tài)規(guī)劃-自底向上

• 狀態(tài)數(shù)組的每一個(gè)狀態(tài)都是代表目標(biāo)金額
• 外層for循環(huán)遍歷所有狀態(tài)的所有取值
• 內(nèi)層for循環(huán)遍歷所有狀態(tài)的所有取值

class Solution {
    public int coinChange(int[] coins, int amount) {
        // int[] dp = new int[amount + 1];

        // 數(shù)組大小是  amount + 1
        int[] dp = new int[amount + 1];
        Arrays.fill(dp,amount + 1);

        // base case
        dp[0] = 0;

        // 外層for循環(huán)在遍歷所有狀態(tài)的所有取值  每一個(gè)狀態(tài)都是目標(biāo)金額
        for(int i = 0; i < dp.length; i++){
            // 內(nèi)層for循環(huán)遍歷所有狀態(tài)的所憂取值
            for(int coin:coins){
                // 子問(wèn)題誤解 直接跳過(guò)
                if(i - coin < 0){
                    continue;
                }

                dp[i] = Math.min(dp[i], dp[i - coin] + 1);
            }
        }

        return (dp[amount] == amount + 1) ? -1 : dp[amount];
    }
}

文章來(lái)源地址http://www.zghlxwxcb.cn/news/detail-691594.html

到了這里，關(guān)于【動(dòng)態(tài)規(guī)劃】322. 零錢(qián)兌換的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！