固定解題步驟+例題精講帶你入門動態規劃

1. 前言

在一周之前，我就開始決定啃動態規劃這塊硬骨頭了，還記得看過y總的動態規劃視頻，當時給我留下了它很難的感覺，我也知道這個程序應該很漫長，但我堅持了一周多幾天了，因此，我想要總結一下這相關內容，也算是為我之后的解相關題目提供更多的思想吧，

2. 動態規劃思想

（1）、什么是動態規劃？

動態規劃是一種在數學、計算機科學和經濟學中使用的，通過把原問題分解為相對簡單的子問題的方式求解復雜問題的方法， 動態規劃常常適用于有重疊子問題和最優子結構性質的問題，動態規劃方法所耗時間往往遠少于樸素解法，

（2）、動態規劃的思想

動態規劃的問題一般形式就是求最值問題還有就是一定具有最優子結構，但也并非不是求最值的就不可以使用動態規劃解決，而動態規劃的主要思想是就是窮舉，但這個窮舉并非是暴力窮舉，它是有技巧的窮舉，那么解題的關鍵是什么呢？解題的關鍵就是狀態的表示（dp陣列的含義）和狀態的轉移計算（狀態轉移方程）（相信看過y總的課的人都知道），

（3）、動態規劃的解題步驟

前提：我們知道了該題可以使用動態規劃解決，

1. 確定相關的狀態（其實就是確定相應的dp陣列的維數和維數相應的含義）和相應的dp陣列的含義，
2. 明確選擇（也就是什么可以使得狀態發生轉變，那么就是列出相關的狀態轉移方程），
3. 還有就是確定相應的base case（也就是一開始就可以確定的，它也是后面狀態轉移的基礎），

（4）、深入理解

我們根據動態規劃的解題步驟，可以看出解這類題目需要確定相應的base case，然后根據這base case并且全程堅信dp陣列的含義（和遞回相信函式的含義一樣），然后根據這兩前提進行狀態轉移，所以他就和數學中的數學歸納法相似，我們先假定其成立，然后在每一步都遵守題目要求，那么我們根據歸納所求出的肯定就是符合題目要求的，然后根據dp陣列的含義就可以求出相應的題目所要求的東西，

3. 例題精講

（1）、 面試題 三步問題

AC代碼：

class Solution {
    public int waysToStep(int n) {
        int m = 1000000007;

        int[] dp = new int[n + 1];
        dp[1] = 1;
        if(n == 1) return dp[1];
        dp[2] = 2;
        if(n == 2) return dp[2];
        dp[3] = 4;
        if(n == 3) return dp[3];

        // 三步問題其實和兩步問題一樣
        // 我們只需要從相應的位置轉化而來，如果是還差三步，我們將它拆分為1 + 2 或者 2 + 1的話，其實和還剩兩步過去 和 還剩一步過去重復了，所以會多算，因為是算方式數，所以只需將其相加不需要再添加任何的常數，
        for(int i = 4; i <= n; i ++){
            dp[i] = ((dp[i - 3] + dp[i - 2]) % m + dp[i - 1]) % m;
        } 

        return dp[n];
    }
}

1. 狀態和dp陣列含義

狀態就是第幾階臺階，那么這里的狀態就是臺階數，一維的，dp陣列的含義：dp[i] 的數值表示的是上到第i階臺階的方式數，一定要相信這個定義，

2. base case

base case 就是一開始就能確定的，即上到第一階的方式數為1，上到第二階臺階的方式數為2，上到第三階臺階的方式數為4，

3. 狀態轉移（計算）

選擇是什么？選擇就是小孩可以一次性上一階、二階、三階，那么第i階臺階可以由 i - 1、i - 2、i - 3 階臺階過來，所以有dp[i] = ((dp[i - 3] + dp[i - 2]) % m + dp[i - 1]) % m，因為最后結果需要取模，所以我們在兩數相加之后就需要取模，

4. 最后的回傳值

根據dp陣列的含義：dp[i] 的數值表示的是上到第i階臺階的方式數，那么所求的就是到第n階臺階的方式數，就是dp[n]，

（2）、 劍指 Offer 連續子陣列的最大和

AC代碼：

class Solution {
    public int maxSubArray(int[] nums) {
        // 
        int[] dp = new int[nums.length];

        dp[0] = nums[0];
        if(nums.length == 0) return dp[0];

        int res = dp[0];

        for(int i = 1; i < dp.length; i ++){
            dp[i] = Math.max(dp[i - 1] + nums[i],nums[i]);
            res = Math.max(res,dp[i]);
        }

        return res;
    }
}

1. 狀態和dp陣列含義

狀態就是以第幾個數結尾的連續子陣列，一維的，dp陣列的含義：dp[i] 值表示的是以第i個數為結尾的連續子陣列的和的最大值，

2. base case

以第一個數結尾的子陣列的和的最大值就是相應陣列中的第一個數的值，

3. 狀態轉移（計算）

這道題的選擇是這個數是否可以加入前面的那個子陣列，那么就是要比較相應的加入后的和與其獨立出來（就是其一個數為一個子陣列）的子陣列的和，dp[i] = Math.max(dp[i - 1] + nums[i],nums[i])；

4. 最后的回傳值

因為要求的是最大值，那么我們需要遍歷一邊dp陣列求最大值，

（3）、不同路徑

AC代碼：

class Solution {
    public int uniquePaths(int m, int n) {
        int[][] dp = new int[m][n];
        // dp[i][j] 表示的是處于 到達第i行第j列上的格子所需的路徑種數
        if(m == 1 && n == 1) return 1;

        // 剛開始的時候，dp[0][0] = 0;
        dp[0][0] = 0;

        // 在處于第一行的位置 除了dp[0][0] 之外的 都是1
        for(int i = 1; i < m; i ++) dp[i][0] = 1;

        // 在處于第一列的位置 除了dp[0][0] 之外的 都是1
        for(int j = 1; j < n; j ++) dp[0][j] = 1;

        for(int i = 1; i < m; i ++){
            for(int j = 1; j < n; j ++){
                // 狀態計算 ： 可以由上面的一個格子和右邊的一個格子轉換而來，
                dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
            }
        }

        return dp[m - 1][n - 1];
    }
}

1. 狀態和dp陣列含義

狀態就是相應的行和列，二維的，dp陣列的含義：dp[i][j] 值表示的是到達第i行第j列上的格子所需的路徑種數，

2. base case

以剛開始的時候，到達第0行第0列的路徑種數為0，因為它是我們的起點，

3. 狀態轉移（計算）

這道題的選擇是機器人每次可以向下或者向右移動一步，那么到達第i行第j列可以從第i行第j - 1列過來，也可以從第i - 1行第j列轉移過來，dp[i][j] = dp[i - 1][j] + dp[i][j - 1]；

4. 最后的回傳值

根據dp陣列的含義：dp[i][j] 值表示的是到達第i行第j列上的格子所需的路徑種數，所以最后所求的是到達第 m - 1行第 n - 1列的路徑種數就是dp[m - 1][n - 1]，

4. 相關LeetCode例題

（1）、 前 n 個數字二進制中 1 的個數

AC代碼：

class Solution {
    public int[] countBits(int n) {
        int[] dp = new int[n + 1];

        dp[0] = 0;
        if(n == 0) return new int[]{dp[0]};

        dp[1] = 1;
        if(n == 1) return new int[]{dp[0],dp[1]};

        dp[2] = 1;
        if(n == 2) return new int[]{dp[0],dp[1],dp[2]};

        int highBit = 2;

        for(int i = 3; i <= n; i ++){
            // 關鍵就是找那個小于i且是2的倍數的最大數
            if(highBit * 2 == i){
                highBit = highBit * 2;
                dp[i] = 1;
                continue;
            }

            dp[i] = dp[i - highBit] + 1;
        }

        return dp;
    }
}

1. 狀態和dp陣列含義

狀態就是相應數字的數值，一維的，dp陣列的含義：dp[i]值表示的是數字的數值為i時，該數字二進制表示中的1的個數，

2. base case

以剛開始的時候，數值為0是dp[0] = 0，數值為1時dp[1] = 1，數值為2時dp[2] = 1，

3. 狀態轉移（計算）

這道題的關鍵就是求出小于且最接近i數值的且為2的倍數的數（即highBit），那么i數值的1的個數只會比i - highBit數值中的個數多1，dp[i] = dp[i - highBit] + 1；

（2）、不同的二叉搜索樹

AC代碼：

class Solution {
    //自己寫出的第一道記憶化搜索
    // num[i] 表示的是長度為i的區間的所能構成的二叉搜索樹的種類數
    int[] num = new int[20];
    public int numTrees(int n) {
        return getNum(1,n);
    }
    
    public int getNum(int start,int end){
        // 長度為1的種類數為1
        if(start > end || start == end){
            num[1] = 1;
            return 1;
        }

        //長度為2的 種類數為2
        if(start + 1 == end){
            num[2] = 2;
            return 2;
        }

        // 備忘錄優化
        if(num[end - start + 1] != 0) 
        {
            //System.out.println(num[end - start + 1]);
            return num[end -start + 1];
        }
        int sum = 0;

        // 如果沒有相應的的備忘就需要添加備忘
        for(int i = start; i <= end; i ++){
            int j = getNum(start,i - 1);
            int k = getNum(i + 1, end);
            // 求總和
            sum += k * j;
        }
        // 記錄下來
        num[end - start + 1] =  sum;//剛開始有點小坑
        return sum;
    }
}

1. 狀態和dp陣列含義

狀態就是區間內部長度，一維的，dp陣列的含義：dp[i]值表示的是區間長度為i的所能形成的二叉搜索樹的種數，

2. base case

以區間長度為1或者為負數時，相應的種類數為1；區間長度為2時，相應的種類數為2，

3. 狀態轉移（計算）

這道題的選擇是我們選舉區間的那一個數為根節點，因為區間的每一個點都可能作為根節點，所以我們在遞回程序中進行列舉，那么分割后在進行求左邊和右邊的區間的所能形成的二叉搜索樹的種類，這個就交給遞回進行完成，那么以該節點為根節點的二叉搜索樹的種類數就是左右所求出的種類數相乘，在進行求和；

4. 備忘錄解決重疊子問題

因為我們求一個區間長度更大的所能形成的二叉搜索樹的種數時是將它進行分割，那么必然會縮小區間，也就是小區間的值會反復使用到，我們會對其進行記錄，從而減少了小區間的反復計算，從而使得效率提高，

5. 結語

經過了一周多的時間，我將動態規劃的簡單題刷完了，并且中等題刷了將近十道，并且動態規劃的好多題型都還沒有熟練掌握，接下來我會繼續努力，其實動態規劃的套路在狀態表示和狀態計算，難也難在狀態表示和狀態計算，其中這需要大量的習題積累，后續動態規劃的文章我也會持續更新，又要去深造了，如果覺得對你有幫助的友友，請留下你的三連，