?算法題

Leetcode 70. 爬樓梯（進(jìn)階版）

題目：

假設(shè)你正在爬樓梯。需要 n 階你才能到達(dá)樓頂。

每次你可以爬至多m (1 <= m < n)個(gè)臺(tái)階。你有多少種不同的方法可以爬到樓頂呢？

注意：給定 n 是一個(gè)正整數(shù)。

輸入描述：輸入共一行，包含兩個(gè)正整數(shù)，分別表示n, m

輸出描述：輸出一個(gè)整數(shù)，表示爬到樓頂?shù)姆椒〝?shù)。

輸入示例：3 2

輸出示例：3

提示：

當(dāng) m = 2，n = 3 時(shí)，n = 3 這表示一共有三個(gè)臺(tái)階，m = 2 代表你每次可以爬一個(gè)臺(tái)階或者兩個(gè)臺(tái)階。

此時(shí)你有三種方法可以爬到樓頂。

• 1 階 + 1 階 + 1 階段
• 1 階 + 2 階
• 2 階 + 1 階

?個(gè)人思路?

這道題是力扣70題的進(jìn)階版本，因?yàn)槊侩A都能重復(fù)使用，所以是一個(gè)完全背包問題，可以用動(dòng)態(tài)規(guī)劃方法解決。

解法

動(dòng)態(tài)規(guī)劃

這里的1階，2階，.... m階就是物品，樓頂就是背包。每一階可以重復(fù)使用，例如跳了1階，還可以繼續(xù)跳1階。所以思路和昨天的題目組合總和四基本就是一道題了。

動(dòng)規(guī)五部曲：

1.確定dp數(shù)組以及下標(biāo)的含義

dp[i]：爬到有i個(gè)臺(tái)階的樓頂，有dp[i]種方法。

2.確定遞推公式

昨天的算法題，也是求裝滿背包有幾種方法，這種遞推公式一般都是dp[i] += dp[i - nums[j]];

而本題呢，dp[i]有幾種來源，dp[i - 1]，dp[i - 2]，dp[i - 3] 等等，即：dp[i - j]；

那么遞推公式為：dp[i] += dp[i - j]

3.dp數(shù)組如何初始化

因?yàn)檫f歸公式是 dp[i] += dp[i - j]，所以dp[0] 一定為1，dp[0]是遞歸中一切數(shù)值的基礎(chǔ)所在，如果dp[0]是0的話，其他數(shù)值都是0了。

下標(biāo)非0的dp[i]初始化為0，因?yàn)閐p[i]是靠dp[i-j]累計(jì)上來的，dp[i]本身為0這樣才不會(huì)影響結(jié)果

4.確定遍歷順序

如果求組合數(shù)就是外層for循環(huán)遍歷物品，內(nèi)層for遍歷背包。

如果求排列數(shù)就是外層for遍歷背包，內(nèi)層for循環(huán)遍歷物品。

這是背包里求排列問題，即：1、2 步 和 2、1 步都是上三個(gè)臺(tái)階，但是這兩種方法不一樣！

所以需將target放在外循環(huán)，將nums放在內(nèi)循環(huán)。每一步可以走多次，這是完全背包，內(nèi)循環(huán)需要從前向后遍歷。

5.舉例來推導(dǎo)dp數(shù)組

import java.util.Scanner;
class climbStairs{
    public static void main(String [] args){
        Scanner sc = new Scanner(System.in);
        int m, n;
        while (sc.hasNextInt()) {
            n = sc.nextInt(); // 從鍵盤輸入?yún)?shù)，中間用空格隔開
            m = sc.nextInt();

            // 求排列問題，先遍歷背包再遍歷物品
            int[] dp = new int[n + 1];
            dp[0] = 1;
            for (int j = 1; j <= n; j++) {
                for (int i = 1; i <= m; i++) {
                    if (j - i >= 0) dp[j] += dp[j - i];
                }
            }
            System.out.println(dp[n]);
        }
    }
}

時(shí)間復(fù)雜度:O(n^2)；（嵌套for循環(huán)）

空間復(fù)雜度:O(?n);（存儲(chǔ)一個(gè)長度為n+1的dp數(shù)組）

?Leetcode ?322. 零錢兌換

題目鏈接:322. 零錢兌換

大佬視頻講解：零錢兌換視頻講解

個(gè)人思路

這道題的每種硬幣的數(shù)量是無限的，典型的完全背包問題。

解法

動(dòng)態(tài)規(guī)劃

動(dòng)規(guī)五部曲：

1.確定dp數(shù)組以及下標(biāo)的含義

dp[j]：湊足總額為j所需錢幣的最少個(gè)數(shù)為dp[j]

2.確定遞推公式

湊足總額為j - coins[i]的最少個(gè)數(shù)為dp[j - coins[i]]，那么只需要加上一個(gè)錢幣coins[i]即dp[j - coins[i]] + 1就是dp[j]（考慮coins[i]）

所以dp[j] 要取所有 dp[j - coins[i]] + 1 中最小的。

遞推公式：dp[j] = min(dp[j - coins[i]] + 1, dp[j]);

3.dp數(shù)組如何初始化

首先湊足總金額為0所需錢幣的個(gè)數(shù)一定是0，那么dp[0] = 0;

因?yàn)槊看稳∽钚〉模?strong>dp[j]必須初始化為一個(gè)最大的數(shù)，否則就會(huì)在min(dp[j - coins[i]] + 1, dp[j])比較的過程中被初始值覆蓋。所以下標(biāo)非0的元素都是應(yīng)該是最大值。

4.確定遍歷順序

本題是求錢幣最小個(gè)數(shù)，那么錢幣有順序和沒有順序都可以，都不影響錢幣的最小個(gè)數(shù)。

這里采用coins放在外循環(huán)，target在內(nèi)循環(huán)的方式。本題錢幣數(shù)量可以無限使用，那么是完全背包。所以遍歷的內(nèi)循環(huán)是正序

5.舉例推導(dǎo)dp數(shù)組

以輸入：coins = [1, 2, 5], amount = 5為例

class Solution {
    public int coinChange(int[] coins, int amount) {
        int max = Integer.MAX_VALUE;
        int[] dp = new int[amount + 1];
       
        for (int j = 0; j < dp.length; j++) { //初始化dp數(shù)組為最大值
            dp[j] = max;
        }
       
        dp[0] = 0; //當(dāng)金額為0時(shí)需要的硬幣數(shù)目為0

        for (int i = 0; i < coins.length; i++) {
            for (int j = coins[i]; j <= amount; j++) {//完全背包->正序遍歷
                if (dp[j - coins[i]] != max) {//只有不是初始最大值時(shí)，該位才有選擇的必要
                    dp[j] = Math.min(dp[j], dp[j - coins[i]] + 1);//選擇硬幣數(shù)目最小的情況

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

時(shí)間復(fù)雜度:O(n^2)；（嵌套for循環(huán)）

空間復(fù)雜度:O(?n);（存儲(chǔ)一個(gè)長度為n+1的dp數(shù)組）

?Leetcode ?279.完全平方數(shù)

題目鏈接:279.完全平方數(shù)

大佬視頻講解：完全平方數(shù)視頻講解

個(gè)人思路

還是完全背包問題，數(shù)字可以重復(fù)使用，和今天的前兩天思路一樣。

解法

動(dòng)態(tài)規(guī)劃

動(dòng)規(guī)五部曲：

1.確定dp數(shù)組（dp table）以及下標(biāo)的含義

dp[j]：和為j的完全平方數(shù)的最少數(shù)量為dp[j]

2.確定遞推公式

dp[j] 可以由dp[j - i * i]推出， dp[j - i * i] + 1 便可以湊成dp[j]。

選擇最小的dp[j]，所以遞推公式：dp[j] = min(dp[j - i * i] + 1, dp[j]);

3.dp數(shù)組如何初始化

dp[0]表示 和為0的完全平方數(shù)的最小數(shù)量，那么dp[0]一定是0。

從遞歸公式dp[j] = min(dp[j - i * i] + 1, dp[j]);中可以看出每次dp[j]都要選最小的，所以非0下標(biāo)的dp[j]一定要初始為最大值，這樣dp[j]在遞推的時(shí)候才不會(huì)被初始值覆蓋。

4.確定遍歷順序

這里只求最小個(gè)數(shù)，所以遍歷順序沒有講究。

5.舉例推導(dǎo)dp數(shù)組

已輸入n為5例，dp狀態(tài)圖如下：

class Solution {
    // 先遍歷物品, 再遍歷背包
    public int numSquares(int n) {
        int max = Integer.MAX_VALUE;
        int[] dp = new int[n + 1];
        
       Arrays.fill(dp, Integer.MAX_VALUE);//初始化

       
        dp[0] = 0; //當(dāng)和為0時(shí)，組合的個(gè)數(shù)為0
        for (int i = 1; i * i <= n; i++) {//遍歷物品
            for (int j = i * i; j <= n; j++) {// 遍歷背包
                if (dp[j - i * i] != max) {
                    dp[j] = Math.min(dp[j], dp[j - i * i] + 1);
                }
            }
        }
        return dp[n];
    }
}

時(shí)間復(fù)雜度:O(n^2)；（嵌套for循環(huán)）

空間復(fù)雜度:O(?n);（存儲(chǔ)一個(gè)長度為n+1的dp數(shù)組）

?以上是個(gè)人的思考反思與總結(jié)，若只想根據(jù)系列題刷，參考卡哥的網(wǎng)址代碼隨想錄算法官網(wǎng)文章來源地址http://www.zghlxwxcb.cn/news/detail-851492.html

到了這里，關(guān)于算法打卡day39|動(dòng)態(tài)規(guī)劃篇07| Leetcode 70. 爬樓梯（進(jìn)階版）、322. 零錢兌換、279.完全平方數(shù)的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！