姓名：譚旭東學號：19011210016

前言

動態(tài)規(guī)劃是什么？

動態(tài)規(guī)劃（dynamic programming）是運籌學的一個分支，是求解決策過程（decision process）最優(yōu)化的數(shù)學方法。
動態(tài)規(guī)劃一般可分為線性動規(guī)，區(qū)域動規(guī)，樹形動規(guī)，背包動規(guī)四類。
動態(tài)規(guī)劃算法通常用于求解具有某種最優(yōu)性質(zhì)的問題。在這類問題中，可能會有許多可行解。每一個解都對應于一個值，我們希望找到具有最優(yōu)值的解。
動態(tài)規(guī)劃算法與分治法類似，其基本思想也是將待求解問題分解成若干個子問題，先求解子問題，然后從這些子問題的解得到原問題的解。

如何學習動態(tài)規(guī)劃？

多刷題，掌握該算法的整體思路
在接下來的內(nèi)容中，我將通過不同的【轉移方程】將動態(tài)規(guī)劃的題目進行分類，讓我們對不同類型的題目有更好的認識

一、簡單相加的狀態(tài)轉移

這類動態(tài)規(guī)劃屬于比較簡單的情況，因為轉移方程可以簡單的直接得到

而且由于新狀態(tài)轉移只需要前幾個狀態(tài)，我們可以壓縮狀態(tài)來節(jié)省更多空間

1. 斐波那契數(shù)列

題目出處：509. 斐波那契數(shù)
轉移方程：【F(n) = F(n - 1) + F(n - 2)】
初始狀態(tài)：【F(0) = 0，F(xiàn)(1) = 1】

不使用狀態(tài)壓縮：

    public int fib(int n) {
        if (n == 0) return 0;
        if ( n == 1 || n == 2) return 1;

        int[] dp = new int[n+1];
    dp[0] = 0;
    dp[1] = 1;

        for (int i = 2; i<=n; i++) {
            dp[i] = f0 + f1;
        }
        return dp[n];
    }

狀態(tài)壓縮后：

    public int fib(int n) {
        if (n == 0) return 0;
        if ( n == 1 || n == 2) return 1;

        int f0 = 0;
        int f1 = 1;

        for (int i = 1; i<n; i++) {
            int newf = f0 + f1;

            f0 = f1;
            f1 = newf;
        }
        return f1;
    }

2. 第 N 個泰波那契數(shù)

題目出處：1137. 第 N 個泰波那契數(shù)
轉移方程：【Tn+3 = Tn + Tn+1 + Tn+2】
初始狀態(tài)：【T0 = 0，T1 = 1，T2 = 1】

直接上狀態(tài)壓縮之后的代碼

    public int tribonacci(int n) {
        if ( n == 0 ) return 0;
        if ( n  <= 2) return 1;

        int t0 = 0;
        int t1 = 1;
        int t2 = 1;

        for (int i = 3; i <= n; i++) {
            
            int newT = t0 + t1 + t2;

            t0 = t1;
            t1 = t2;
            t2 = newT;
        }
        return t2;
    }

3. 爬樓梯

題目出處：70. 爬樓梯
轉移方程：【dp[n] = dp[n-1] + dp[n-2]】
初始狀態(tài)：【dp[1] = 1，dp[2] = 2】

狀態(tài)壓縮后的代碼：

    public int climbStairs(int n) {
        if (n == 1) return 1;
        if (n == 2) return 2; 


        int dp1 = 1;
        int dp2 = 2;

        for (int i = 3; i <= n; i++) {
            int newDp = dp1 + dp2;
            dp1 = dp2;
            dp2 = newDp;
        }

        return dp2;
    }

二、取max/min的狀態(tài)轉移

這種狀態(tài)轉移方程需要在轉移過程中選取最小/最大值

1. 最小花費爬樓梯

題目出處：746. 使用最小花費爬樓梯
狀態(tài)轉移：【dp[i] = min{ dp[i-1]+cost[i-1] , dp[i-2]+cost[i-2]}】
- 分析：能夠從第i-1個臺階爬到本臺階，也能從第i-2個臺階爬到本臺階；爬的時候分別加上對應的cost即可
初始狀態(tài)：【dp[0] = 0 , dp[1] = 1】

只需要前兩個狀態(tài)，所以還是可以狀態(tài)壓縮（注釋掉的是沒進行狀態(tài)壓縮的版本）

    public int minCostClimbingStairs(int[] cost) {

        int len = cost.length;

        if (len == 1) return 0;
        if (len == 2) return Math.min(cost[0],cost[1]);


        // int[] dp = new int[len + 1];

        int dp1 = 0;
        int dp2 = 0;

        for (int i = 2; i<=len; i++) {
            // dp[i] = Math.min(dp[i-1]+cost[i-1],dp[i-2]+cost[i-2]);
            int newdp = Math.min(dp1+cost[i-2],dp2+cost[i-1]);

            dp1 = dp2;
            dp2 = newdp;

        }
        // return dp[len];
        return dp2;
    }

2. 打家劫舍

題目出處：198. 打家劫舍
轉移方程：【dp[i] = max{dp[i-2] + nums[i] , dp[i-1]}】
- 分析：因為不能連著搶劫，所以可以【搶第i-2家和第i家的，那么收益為dp[i-2] + nums[i]】，或者【第i家的不搶，那么收益仍未dp[i-1]】
初始狀態(tài)：【dp[0] = nums[0]，dp[1] = max{nums[0]，nums[1]}】

代碼如下，狀態(tài)壓縮版本（注釋掉的是非狀態(tài)壓縮版）

    public int rob(int[] nums) {
        
        int len = nums.length;

        if (len == 1) return nums[0];
        if (len == 2) return Math.max(nums[0],nums[1]);


        // int[] dp = new int[len];
        // dp[0] = nums[0];
        // dp[1] = Math.max(nums[0],nums[1]);

        int dp0 = nums[0];
        int dp1 = Math.max(nums[0],nums[1]);

        for (int i = 2; i < len; i++) {
            // dp[i] = Math.max(dp[i-1] , dp[i-2] + nums[i]);
            int newDp = Math.max(dp1 , dp0 + nums[i]);

            dp0 = dp1;
            dp1 = newDp;
        }

        // return dp[len-1];
        return dp1;

    }

3. 打家劫舍2

題目出處：213. 打家劫舍 II
狀態(tài)轉移：和上題一致
初始狀態(tài)：和上題一致

不同點在于：這里的房屋（數(shù)組）是首尾相連的，也就是說打劫了第一家，就不能打劫最后一家；打劫了最后一家，就不能打劫第一家

根據(jù)這種情況，我們將數(shù)組分為nums[0,len-1]和nums[1,len]，然后分別通過上一題的方式進行求解，然后返回兩個解的最大值即可

代碼如下

    public int rob(int[] nums) {
        
        int n = nums.length;

        if (n == 1) return nums[0];
        if (n == 2) return Math.max(nums[0],nums[1]);


        int[] nums1 = Arrays.copyOfRange(nums , 0 , n - 1);
        int[] nums2 = Arrays.copyOfRange(nums , 1 , n);

        int ans1 = findMax(nums1);
        int ans2 = findMax(nums2);

        return Math.max(ans1 , ans2);
    }

    public int findMax(int[] nums) {

        int n = nums.length;

        if (n == 2) return Math.max(nums[0] , nums[1]);



        int dp0 = nums[0];
        int dp1 = Math.max(nums[0],nums[1]);

        for (int i = 2 ; i < n; i++) {
            int newdp = Math.max(dp1,dp0 + nums[i]);

            dp0 = dp1;
            dp1 = newdp;
        }

        return dp1;
    }

4. 刪除并獲得點數(shù)

題目出處：740. 刪除并獲得點數(shù)
狀態(tài)轉移：【dp[i] = max{ dp[i-1] , dp[i-2] + count[i]*i }】
- ① 這里我們將題目轉換一種思路，相當于打家劫舍的進階版，也就是說我們不能夠選擇相鄰的元素
- ② 我們需要先得到nums[]數(shù)組中的最大值max，然后將nums[]數(shù)組轉換成為count[]數(shù)組，統(tǒng)計每個數(shù)字出現(xiàn)的次數(shù)（count[]數(shù)組的大小為【max+1】，從1~max）
- ③ 然后我們開始狀態(tài)轉移過程：可以從i-1狀態(tài)轉移到目前狀態(tài)，由于不能夠連著選數(shù)字，所以這種情況下收益為【dp[i-1]】；或者從i-2狀態(tài)轉移到目前狀態(tài)，那么目前狀態(tài)是可以選上的，所以當前收益為【dp[i-2] + count[i] * i】
初始狀態(tài)：
- dp[1] = count[1] * 1
- dp[2] = max{count[1] * 1，count[2] * 2}

代碼如下：

    public int deleteAndEarn(int[] nums) {

        int max = 0;

        for (int i = 0; i < nums.length; i++) {
            max = Math.max(max, nums[i]);
        }

        if (max == 1) return nums.length;

        int[] count = new int[max + 1];
        int[] dp = new int[max + 1];

        for (int i = 0; i < nums.length; i++) {
            ++count[nums[i]];
        }

        dp[1] = count[1];
        dp[2] = Math.max(count[1], count[2] * 2);

        for (int i = 3; i <= max; i++) {
            dp[i] = Math.max(dp[i - 2] + count[i] * i, dp[i - 1]);
        }

        return dp[max];
    }

三、嵌套的狀態(tài)轉移

這種DP的狀態(tài)轉移，會和之前的所有狀態(tài)有關，不可進行狀態(tài)壓縮

1. 跳躍游戲2

題目出處：45. 跳躍游戲 II
狀態(tài)轉移：dp[i]表示跳到i位置所需的最小步數(shù)
- ① 求dp[i]時，目前狀態(tài)的值和之前的所有狀態(tài)值都有關
- ② 遍歷之前所有的節(jié)點，如果不能跳到本節(jié)點，則跳過
- ③ 如果j節(jié)點能夠跳到本節(jié)點，即【j + nums[j] >= i】
- ④ 對所有能夠跳到本節(jié)點的前置j節(jié)點，推導得到【dp[i] = min{dp[i],dp[j]+1}】
初始狀態(tài)：
- ① dp[0] = 0;
- ② 其他節(jié)點假設不可達，設置成為Integer.MAX_VALUE

動態(tài)規(guī)劃版本的代碼如下：


    public int jump(int[] nums) {

        int len = nums.length;

        if (len == 1) return 0;


        int[] dp = new int[len];
        Arrays.fill(dp, Integer.MAX_VALUE);

        dp[0] = 0;

        for (int i = 1; i < len; i++) {

            for (int j = 0; j < i; j++) {

                if (j + nums[j] >= i)
                    dp[i] = Math.min(dp[i], dp[j] + 1);
            }
        }

        return dp[len - 1];
    }

其實該題目還能用BFS去做，不斷對節(jié)點松弛，有點類似于SPFA算法，代碼如下：

    public int jump(int[] nums) {
        int len = nums.length;
        int[] d = new int[len];
        Arrays.fill(d, Integer.MAX_VALUE);
        d[len - 1] = 0;
        Queue<Integer> queue = new LinkedList<>();
        queue.offer(len - 1);

        while (!queue.isEmpty()) {
            int cur = queue.poll();
            for (int i = 0; i < len; i++) {
                if (nums[i] >= cur - i) {       // 判斷能否到達
                    if (d[cur] + 1 < d[i]) {    // 是否松弛成功，成功才入隊
                        d[i] = d[cur] + 1;
                        queue.add(i);
                    }
                }
            }
        }
        return d[0];
    }

四、連續(xù)子數(shù)組狀態(tài)轉移

這類題目往往要求連續(xù)子數(shù)組的最大/最小和值，我們在遍歷數(shù)組時通過一個sum（子數(shù)組和）值不斷更新最大/最小值，最后可以得到結果

1. 最大子序和

題目出處：53. 最大子序和
狀態(tài)轉移：
- ① 設置一個sum值，作為我們目前的子數(shù)組和
- ② 遍歷數(shù)組，我們需要求的是最大值，那么我們可以很簡單的分析出，最大子數(shù)組肯定不是以負數(shù)開頭或者結尾的（除非只有負數(shù)）
- ③ 再進一步推導，如果前置的某個子數(shù)組為負數(shù)，我們可以將它合并，那么它對我們接下來需要尋找的最大值是沒有一點正面的幫助的，需要舍棄掉，繼續(xù)從當前位置開始往下找
- ④ 也就是說，如果【sum <= 0】，那么我們從當前位置往下找即【sum = nums[i]】
- ⑤ 如果【sum > 0】，那么不管【nums[i]】是正還是負，我們都可以把它加到我們的子數(shù)組中去
- ⑥ 為什么負數(shù)還要加進去？是因為可能出現(xiàn)一個很小的負數(shù)，但是前面的正數(shù)卻很大的情況，如[100,-1,100]；如果遇到負數(shù)我們就重新開始的話，是有可能出現(xiàn)撿了芝麻丟了西瓜的情況的
- ⑦ 如果前面的正數(shù)很小，而負數(shù)卻很大的話，如[-100,1,1]；那么這種情況我們通過④就能夠切斷掉前面的很大的負數(shù)

要用語言表達思路，實在是...
還是直接上代碼把，要去品...

    public int maxSubArray(int[] nums) {

        int ans = Integer.MIN_VALUE;
        int sum = 0;

        for(int i=0; i< nums.length; i++) {
            if (sum <= 0) {
                sum = nums[i];
            } else {
                sum += nums[i];
            }

            ans = Math.max(ans , sum);
        }
        return ans;
    }

2. 環(huán)形子數(shù)組的最大和

思路：其實和上題基本一致，但是由于這里是首尾相連，我們需要分情況討論

（1）最大和子數(shù)組出現(xiàn)在中間：
- ① 這種情況，包含了首尾都不選（首尾都為負），或者首尾只選一個的情況（首尾其中一個為負）
- ② 如果全都是正數(shù)，那么這種情況還包含了首尾都選的情況
- ③ 我們可以直接通過上一題的思路，求出這種情況下的最大值max

（2）最大子數(shù)組和出現(xiàn)在兩端：
- ① 這種情況的意思是，最大子數(shù)組同時包含了首尾元素，還可能往數(shù)組中間延申
- ② 假設整個數(shù)組所有數(shù)的和為sum
- ③ 如果兩端的和是最大的，那么中間的和就是最小的！
- ④ 我們只需要按照上一題的邏輯，在數(shù)組中間求出連續(xù)數(shù)組的最小值和值min，最后【sum - min】就是數(shù)組剩下元素的最大和值

代碼：注意，求第二種情況需要去掉首尾元素！

    public int maxSubarraySumCircular(int[] nums) {

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

        int max = Integer.MIN_VALUE;
        int min = Integer.MAX_VALUE;

        int sum1 = 0;
        int sum2 = 0;

        int sum = 0;

        for (int i = 0; i < nums.length; i++) {

            sum += nums[i];

            if (sum1 <= 0)
                sum1 = nums[i];
            else
                sum1 += nums[i];

            max = Math.max(max, sum1);
        }


        for (int i = 1; i < nums.length - 1; i++) {

            if (sum2 >= 0)
                sum2 = nums[i];
            else
                sum2 += nums[i];

            min = Math.min(min, sum2);
        }

        return Math.max(sum - min, max);
    }

3. 乘積最大的子數(shù)組

題目出處：152. 乘積最大子數(shù)組
轉移方程：【preMax = max{preMax * nums[i]，preMin * nums[i]}】，【preMin = min{preMax * nums[i]，preMin * nums[i]}】
- ① 由于數(shù)組中的元素有正有負，負數(shù)的存在可能會導致最大值max變最小值min，最小值min變最大值
- ② 所以在尋找子序列的過程中，維護最大值preMax和最小值preMin，表示前綴最大/最小值
- ③ 還需要考慮一種情況即【nums[i] = 0】，后面的乘積都為0了，需要從下一個數(shù)開始繼續(xù)取，這種情況下我們下一次的preMax和preMin直接從nums[i+1]開始
初始狀態(tài)：【preMax = nums[0]】【preMin = nums[0]】

    public int maxProduct(int[] nums) {

        int max = nums[0];

        // 前置最大最小乘積
        int preMax = nums[0];
        int preMin = nums[0];

        int len = nums.length;

        for (int i = 1; i < len; i++) {


            /**
             * 當前的最大最小值
             * 可能由前置的最大最小值乘以正數(shù)/負數(shù)得到
             */
            int curMax = Math.max(preMax * nums[i], preMin * nums[i]);
            int curMin = Math.min(preMax * nums[i], preMin * nums[i]);

            /**
             * 是0的情況，會從nums[i+1]重新開始
             * 所以我們需要加入以下語句，以免curMax和curMin都為0
             * 之后乘積就全部為0了
             */
            preMax = Math.max(nums[i], curMax);
            preMin = Math.min(nums[i], curMin);

            max = Math.max(preMax, max);
        }
        return max;
    }

4. 乘積為正數(shù)的最長子數(shù)組

題目出處：1014. 最佳觀光組合
轉移方程：
- ① 乘積要為正數(shù)，那么同上一題一樣，根據(jù)nums[i]的不同情況分類，我們需要維護兩個數(shù)組postive[i]和negative[i]，分別表示以nums[i]結尾的子數(shù)組，前面連續(xù)最長的正數(shù)/負數(shù)乘積為多少
- ② 如果【nums[i] = 0】，那么子數(shù)組需要從下一個開始進行計算，即【postive[i] = 0】【negative[i] = 0】
- ③ 如果【nums[i] > 0】，那么【postive[i] = postive[i-1] + 1】，【negative[i] = negative[i-1] + 1】（特殊情況：如果negative[i-1] = 0，說明前面子數(shù)組長度為0，那么【negative[i] = 0】）
- ④ 如果【nums[i] < 0】，那么【negative[i] = negative[i-1] + 1】，【positive[i] = negative[i-1] + 1】（特殊情況：如果negative[i-1] = 0，說明前面子數(shù)組長度為0，那么【positive[i] = 0】）
初始狀態(tài)：
- nums[0]大于0時，將positive[0]置1
- nums[0]小于0時，將negative[0]置1

    public int getMaxLen(int[] nums) {

        int len = nums.length;

        int[] pos = new int[len];
        int[] neg = new int[len];

        // 初始化
        if (nums[0] > 0) pos[0] = 1;
        else if (nums[0] < 0) neg[0] = 1;

        int max = pos[0];

        for (int i = 1; i < len; i++) {
            if (nums[i] > 0) {
                pos[i] = pos[i - 1] + 1;
                neg[i] = neg[i - 1] == 0 ? 0 : neg[i - 1] + 1;
            } else if (nums[i] < 0) {
                pos[i] = neg[i - 1] == 0 ? 0 : neg[i - 1] + 1;
                neg[i] = pos[i - 1] + 1;
            } else {
                pos[i] = 0;
                neg[i] = 0;
            }
            max = Math.max(max, pos[i]);
        }

        return max;
    }

5. 最佳觀光組合

1014. 最佳觀光組合
狀態(tài)轉移：觀光得分：【values[i] + values[j] + i - j】
- ① 將上述得分拆分成為兩個部分，對于j位置來說，我們只需要知道前置最大的【values[i] + i】即可
- ② 通過記錄max{values[i] + i}，然后遍歷數(shù)組，我們可以只進行一次遍歷就求得結果
初始狀態(tài)：【maxVi = values[0] + 0】

其實這題的總體思路就是在遍歷過程中維護一個最大值
代碼如下：

    public int maxScoreSightseeingPair(int[] values) {
        int ans = 0;
        int maxVi = values[0] + 0;

        for (int j = 1; j < values.length; j++) {
            ans = Math.max(ans , maxVi + values[j] - j);

            if (values[j] + j > maxVi)
                maxVi = (values[j] + j);
        }
        return ans;
    }

五、買賣股票問題

這類題目模擬股票的買入和賣出，其實就是要我們對股票的狀態(tài)進行一個模擬，實現(xiàn)完整的過程并且將所有結果模擬出來進行對比

1. 買賣股票的最佳時機

題目出處：121. 買賣股票的最佳時機
- 一支股票，一買一賣（也可以不買）

狀態(tài)轉移：維護二維數(shù)組dp[prices.length][2]
- ① 第一層狀態(tài)i表示到第i天能夠獲得的最大收益
- ② 第二層狀態(tài)標識該天股票的持有情況，0表示未持有，1表示已持有
- ③ 當前未買入狀態(tài)【dp[i][0]】可以由兩種狀態(tài)轉移而來，取兩者最大值
 - 前一天也未持有：【dp[i-1][0]】
 - 前一天已經(jīng)持有，今天賣出：【dp[i-1][1] + price[i]】
- ④ 當前買入狀態(tài)【dp[i][1]】可以由兩種狀態(tài)轉移而來
 - 前一天已經(jīng)持有：【dp[i-1][1]】
 - 前一天未持有，今天買入：【dp[i-1][0] - price[i]】（需要更改）
 - 注意：這里由于我們只能單次買入賣出股票，所以買入股票這個操作是無前效性的，我們需要更改最后一種狀態(tài)為【-price[i]】

初始狀態(tài)：
- 【dp[0][0] = 0】
- 【dp[0][1] = -prices[0]】（第一天就買入）

代碼：

    public int maxProfit(int[] prices) {

        int len = prices.length;

        int[][] dp = new int[len][2];

        dp[0][0] = 0;
        dp[0][1] = -prices[0];

        for (int i = 1; i<len; i++) {
            dp[i][0] = Math.max(dp[i-1][0] , dp[i-1][1] + prices[i]);
            dp[i][1] = Math.max(dp[i-1][1] , -prices[i]);
        }

        return dp[len - 1][0];
    }

2. 買賣股票的最佳時機2

題目出處：122. 買賣股票的最佳時機 II
狀態(tài)轉移：一次只能持有一支股票，可以多次買賣
- 上一題已經(jīng)分析得到這個的轉移狀態(tài)方程了
- 【dp[i][0] = Math.max(dp[i-1][0] , dp[i-1][1] + prices[i])】
- 【dp[i][1] = Math.max(dp[i-1][1] , dp[i-1][0] - prices[i])】

    public int maxProfit(int[] prices) {

        int len = prices.length;

        int[][] dp = new int[len][2];

        dp[0][0] = 0;
        dp[0][1] = -prices[0];

        for (int i = 1; i<len; i++) {
            dp[i][0] = Math.max(dp[i-1][0] , dp[i-1][1] + prices[i]);
            dp[i][1] = Math.max(dp[i-1][1] , dp[i-1][0] - prices[i]);
        }

        return dp[len - 1][0];
    }

3. 最佳買賣股票時機含冷凍期

題目出處：309. 最佳買賣股票時機含冷凍期
狀態(tài)轉移：加入冷凍期，時長為1天，也就是說前一天賣出股票，后一天無法再買入；一次最多持有一支股票，可以多次買入賣出
- ① 維護轉移數(shù)組dp[n][2]，n為天數(shù)，0表示未持有非冷凍期，1表示持有，2表示未持有但是處在冷凍期內(nèi)
- ② 今天不持有股票且非冷凍期：前一天也不持有，分為兩種情況，前一天是冷凍期和前一天不是冷凍期；所以【dp[i][0] = max{dp[i-1][0]，dp[i-1][2]}】
- ③ 今天持有股票：前一天也持有股票，或者前一天不持有股票，今天買入股票；所以【dp[i][1] = max{dp[i-1][1]，dp[i-1][0]-price[i]}】
- ③ 今天持有股票且在冷凍期內(nèi)：前一天持有股票，且賣出；所以【dp[i][2] = dp[i-1][1] + price[i]】
初始狀態(tài)：第一天肯定是沒有冷凍期的
- dp[0][0] = 0
- dp[0][1] = -price[0]
- dp[0][2] = 0

    public int maxProfit(int[] prices) {

        int len = prices.length;

        int[][] dp = new int[len][3];

        dp[0][0] = 0;
        dp[0][1] = -prices[0];
        dp[0][2] = 0;

        for (int i = 1; i < len; i++) {
            dp[i][0] = Math.max(dp[i - 1][0], dp[i - 1][2]);
            dp[i][1] = Math.max(dp[i - 1][1], dp[i - 1][0] - prices[i]);
            dp[i][2] = dp[i - 1][1] + prices[i];
        }

        return Math.max(dp[len - 1][0], Math.max(dp[len - 1][1], dp[len - 1][2]));
    }

4. 買賣股票的最佳時機含手續(xù)費

題目出處：714. 買賣股票的最佳時機含手續(xù)費
轉移方程：一次最多購買一支股票，可以多次買入賣出；每次交易（買入+賣出）都需要支付一定的手續(xù)費，其實也可以理解為賣出要收錢
- ① 正常轉移，加上手續(xù)費即可
- ② 【dp[i][0] = max{dp[i-1][0]，dp[i-1][1] + price[i] - fee}】
- ③ 【dp[i][1] = max{dp[i-1][1]，dp[i-1][0] - price[i]}】
初始狀態(tài)：dp[0][0] = 0，dp[0][1] = -price[0]

    public int maxProfit4(int[] prices, int fee) {

        int len = prices.length;

        int[][] dp = new int[len][2];

        dp[0][0] = 0;
        dp[0][1] = -prices[0];

        for (int i = 1; i < len; i++) {
            dp[i][0] = Math.max(dp[i - 1][0], dp[i - 1][1] + prices[i] - fee);
            dp[i][1] = Math.max(dp[i - 1][1], dp[i - 1][0] - prices[i]);
        }
        return dp[len - 1][0];
    }

六、0-1背包問題

基本概念：

最基本的背包問題就是 01 背包問題：一共有 N 件物品，第 i（i 從 1 開始）件物品的重量為 w[i]，價值為 v[i]。在總重量不超過背包承載上限 W 的情況下，能夠裝入背包的最大價值是多少？
- 如果是 01 背包，即數(shù)組中的元素不可重復使用，外循環(huán)遍歷 arrs，內(nèi)循環(huán)遍歷 target，且內(nèi)循環(huán)倒序 （因為這里nums中一個元素只能用一次，循環(huán)過了就相當于取用過了，不再選了）

1. 分割等和子集

題目出處：416. 分割等和子集
思路：只要找到一個子集，其和剛好為sum/2即可
- ① 我們維護一個【dp[n+1]】數(shù)組，表示從0~n的數(shù)是否可以由nums數(shù)組中的數(shù)組成（這里n=sum/2）
- ② 外層循環(huán)nums，嵌套內(nèi)循環(huán)倒序遍歷dp[i]，在nums中找能夠組成i的集合是否存在；也就說說我們一個一個數(shù)取出來，然后看這個數(shù)在范圍 [0-target]內(nèi)，能和前面已存在的結果構成什么新的結果。
- ③ 【dp[i] = dp[i] || dp[i - num]】，之所以要或上一個dp[i]，是因為結果具有前效性，也就是說如果早就拼湊出來了這個子集，要覆蓋后面的結果使其為true

    public boolean canPartition(int[] nums) {
        int len = nums.length;
        int sum = 0;

        for (int i = 0; i < len; i++) sum += nums[i];

        if (sum % 2 == 1) return false;     // 奇數(shù)無法二分

        int target = sum / 2;

        boolean[] dp = new boolean[target + 1];
        dp[0] = true;
    
    
        for (int num : nums) {
            for (int i = target; i >= num; --i) {
                if (i - num >= 0) {
                    dp[i] = dp[i] || dp[i - num];
                }
            }
        }
        return dp[target];
    }

2. 目標和

題目出處：494. 目標和
- 題目的不同之處在于：選擇數(shù)字的時候可以進行加或者減，所以我們維護的數(shù)組長度需要大于target了，至少得是數(shù)組和【sum】
思路1：我們想辦法把這一題轉換為上一題的思路，分析一下有什么不同
- ① 首先，所有的數(shù)字都一定要用上一次，去構建目標和
- ② 其次，使用該數(shù)字的時候可以選擇其前面的符號為正或者負
- ③ 我們假設【target = x - y】，即x為正數(shù)部分總和，y為負數(shù)部分總和
- ④ 同時可以得到【sum = x + y】，也就是整體總和
- ⑤ 【（target + sum）/2 = x】，也就是說我們只要在數(shù)組中找到一個子數(shù)組，其和為x，構成正數(shù)部分，那么剩下的和就為y，構成負數(shù)部分
- ⑥ 經(jīng)過上述分析，我們將target轉換為x，就可以套用上一題的思路

    public int findTargetSumWays(int[] nums, int target) {

        int len = nums.length;

        int sum = 0;
        for (int i = 0; i < len; i++) sum += nums[i];

        if (target > sum || target < -sum || (target + sum) % 2 == 1) return 0;
        int x = (sum + target) / 2;

        int[] dp = new int[x + 1];
        dp[0] = 1;                      // 目標和為0，可以不選，故總共有一種方案

        for (int num : nums) {
            for (int i = x; i >= num; --i) {
                dp[i] += dp[i - num];
            }
        }
        return dp[x];
    }

思路2：當然還有一種做法，即擴大范圍進行統(tǒng)計[-sum，sum]，然后每次狀態(tài)轉移時加上正負兩種情況
- ① 維護二維數(shù)組dp[i][j]，其中i表示只考慮前i個數(shù)數(shù)字（數(shù)字需要全部用完），j表示能夠構成結果為j的方案數(shù)量
- ② 其中i的范圍為[0，len+1]，j的范圍為[-sum，sum]
- ③ 由于是0-1背包問題，所以外層循環(huán)取num，內(nèi)層循環(huán)更新方案數(shù)量，需要同時考慮加減兩種方案

    public int findTargetSumWays2(int[] nums, int target) {
        int len = nums.length;

        int sum = 0;

        for (int i = 0; i < len; i++) sum += nums[i];

        if (target > sum || target < -sum) return 0;

        // i表示使用了前幾個數(shù)組num
        // j表示能夠構成的結果，范圍為-sum到sum，下面使用時需要加入偏移量
        int[][] dp = new int[len + 1][sum * 2 + 1];
        dp[0][sum] = 1;     // 使用0個元素構成0，方案有一種

        for (int i = 1; i <= len; i++) {
            int num = nums[i - 1];
            for (int j = -sum; j <= sum; j++) {
                if (j + sum - num >= 0)
                    dp[i][j + sum] += dp[i - 1][j + sum - num];
                if (j + sum + num <= 2 * sum)
                    dp[i][j + sum] += dp[i - 1][j + sum + num];
            }
        }

        // 所有數(shù)都用上，能構成target的方案數(shù)量
        return dp[len][target + sum];
    }

七、完全背包問題

基本概念：

完全背包與 01 背包不同就是每種物品可以有無限多個：一共有 N 種物品，每種物品有無限多個，第 i（i 從 1 開始）種物品的重量為 w[i]，價值為 v[i]。在總重量不超過背包承載上限 W 的情況下，能夠裝入背包的最大價值是多少？
一般就是要我們在arr[]數(shù)組中找出能夠組成target的組合
- （1）如果是完全背包，即數(shù)組中的元素可重復使用并且不考慮元素之間順序，arrs 放在外循環(huán)（保證 arrs 按順序），target在內(nèi)循環(huán)。且內(nèi)循環(huán)正序。
- （2）如果組合問題需考慮元素之間的順序，需將 target 放在外循環(huán)，將 arrs 放在內(nèi)循環(huán)，且內(nèi)循環(huán)正序

1. 單詞拆分

題目出處：139. 單詞拆分
思路：判斷一個字符串s是否能夠拆分成為一個或者多個在字典wordDict中出現(xiàn)的單詞
- ① 維護一個數(shù)組dp[i]，表示字符串i以及其之前的字串能否由wordDict中的串組成，i的范圍為[0，s.len]
- ② 外層循環(huán)遍歷目標字符串s，內(nèi)層循環(huán)遍歷字典wordDict（字典中元素可重復使用）
- ③ dp[i] = dp[i-len] || dp[i]（這里的len為字典中某個字符的長度）

    public boolean wordBreak(String s, List<String> wordDict) {
        int len = s.length();

        boolean[] dp = new boolean[len + 1];
        dp[0] = true;

        for (int i = 1; i <= len; i++) {
            for (String curS : wordDict) {
                int size = curS.length();

                if (i - size >= 0 && s.substring(i - size, i).equals(curS))
                    dp[i] = dp[i] || dp[i - size];
            }
        }
        return dp[len];
    }

2. 完全平方數(shù)

題目出處：279. 完全平方數(shù)
思路：將題目轉換成為從數(shù)組nums[1，sqrt(n)]中，選出平方數(shù)能夠組成target的組合，并且使組合中數(shù)量個數(shù)最小
- ① 維護一個dp[i]數(shù)組，i組成的結果，dp[i]表示組成結果i需要的最少數(shù)量
- ② 數(shù)組nums中的元素是可以重復使用的，所以為完全背包問題
- ③ 外層循環(huán)遍歷nums取數(shù)，內(nèi)層循環(huán)找不同的組合方案（從0-target中任意一個數(shù)轉換到target都可以使方案+1）
- ④ 初始狀態(tài)dp[0] = 0，表示結果為0的完全平方數(shù)和組合為0個，其余都為無窮大（方便取min）
- ⑤ 【dp[i] = min{dp[i]，dp[i-num*num] + 1}】

    public int numSquares(int n) {

        int[] dp = new int[n + 1];
        Arrays.fill(dp, Integer.MAX_VALUE);
        dp[0] = 0;

        for (int num = 1; num <= Math.sqrt(n); num++) {
            int squareNum = num * num;
            for (int i = 0; i <= n; i++) {
                if (i - squareNum >= 0)
                    dp[i] = Math.min(dp[i], dp[i - squareNum] + 1);
            }
        }
        return dp[n];
    }

3. 組合總和

題目出處：377. 組合總和 Ⅳ
思路：nums中的數(shù)字可以重復選取，不同的順序組成的組合是不一樣的
- ① 維護數(shù)組dp[i]，表示組成和為i的組合數(shù)量
- ② 在這個題目中，由于不同的選擇順序認作不同的結果，所以我們在外層遍歷dp[]數(shù)組，在內(nèi)層遍歷nums數(shù)組，這樣的話可以表示不同的組合順序
- ③ 【dp[i] = dp[i] + dp[i-num]】

4. 零錢兌換

題目出處：322. 零錢兌換
思路：每種硬幣是無限的，需要返回能夠構成指定amount額度的最小硬幣數(shù)量
- ① 維護dp[i]數(shù)組，表示構成額度i所需的最少硬幣數(shù)量
- ② 由于硬幣可以無限使用，我們將dp[]放在外層循環(huán)，將coin放在內(nèi)層循環(huán)

    public int coinChange(int[] coins, int amount) {
        int[] dp = new int[amount + 1];
        Arrays.fill(dp, 100000);        // 如果填充MAX_VALUE，可能需要考慮反轉問題，所以隨便找一個大數(shù)填入
        dp[0] = 0;      // 沒有面額為0的硬幣

        for (int i = 1; i <= amount; i++) {

            for (int coin : coins) {
                if (i - coin >= 0) {
                    dp[i] = Math.min(dp[i], dp[i - coin] + 1);
                }
            }
        }

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

5. 零錢兌換2

題目出處：518. 零錢兌換 II
思路：這題和上一題不一樣之處在于，在本題目中重復的組合是需要排除掉的
- ① 維護dp[i]數(shù)組，表示構成額度i的組合數(shù)量有多少
- ② 我們只需要改變一下遍歷的順序，外層循環(huán)遍歷coins[]數(shù)組，內(nèi)層循環(huán)遍歷dp[]數(shù)組
- ③ 初始狀態(tài)，dp[0] = 1，表示組成總額度為0的組合有1種（不選）

    public int change(int amount, int[] coins) {
        int[] dp = new int[amount + 1];
        dp[0] = 1;

        for (int coin : coins) {
            for (int i = 1; i <= amount; i++) {
                if (i - coin >= 0)
                    dp[i] += dp[i - coin];
            }
        }
        return dp[amount];
    }

``

···java

色偷偷精品伊人,欧洲久久精品,欧美综合婷婷骚逼,国产AV主播,国产最新探花在线,九色在线视频一区,伊人大交九欧美,1769亚洲,黄色成人av

經(jīng)典算法——動態(tài)規(guī)劃

經(jīng)典算法——動態(tài)規(guī)劃

前言

一、簡單相加的狀態(tài)轉移

1. 斐波那契數(shù)列

2. 第 N 個泰波那契數(shù)

3. 爬樓梯

二、取max/min的狀態(tài)轉移

1. 最小花費爬樓梯

2. 打家劫舍

3. 打家劫舍2

4. 刪除并獲得點數(shù)

三、嵌套的狀態(tài)轉移

1. 跳躍游戲2

四、連續(xù)子數(shù)組狀態(tài)轉移

1. 最大子序和

2. 環(huán)形子數(shù)組的最大和

3. 乘積最大的子數(shù)組

4. 乘積為正數(shù)的最長子數(shù)組

5. 最佳觀光組合

五、買賣股票問題

1. 買賣股票的最佳時機

2. 買賣股票的最佳時機2

3. 最佳買賣股票時機含冷凍期

4. 買賣股票的最佳時機含手續(xù)費

六、0-1背包問題

1. 分割等和子集

2. 目標和

七、完全背包問題

1. 單詞拆分

2. 完全平方數(shù)

3. 組合總和

4. 零錢兌換

5. 零錢兌換2

相關閱讀更多精彩內(nèi)容

友情鏈接更多精彩內(nèi)容

色偷偷精品伊人,欧洲久久精品,欧美综合婷婷骚逼,国产AV主播,国产最新探花在线,九色在线视频一区,伊人大交九 欧美,1769亚洲,黄色成人av

經(jīng)典算法——動態(tài)規(guī)劃

前言

一、簡單相加的狀態(tài)轉移

1. 斐波那契數(shù)列

2. 第 N 個泰波那契數(shù)

3. 爬樓梯

二、取max/min的狀態(tài)轉移

1. 最小花費爬樓梯

2. 打家劫舍

3. 打家劫舍2

4. 刪除并獲得點數(shù)

三、嵌套的狀態(tài)轉移

1. 跳躍游戲2

四、連續(xù)子數(shù)組狀態(tài)轉移

1. 最大子序和

2. 環(huán)形子數(shù)組的最大和

3. 乘積最大的子數(shù)組

4. 乘積為正數(shù)的最長子數(shù)組

5. 最佳觀光組合

五、 買賣股票問題

1. 買賣股票的最佳時機

2. 買賣股票的最佳時機2

3. 最佳買賣股票時機含冷凍期

4. 買賣股票的最佳時機含手續(xù)費

六、0-1背包問題

1. 分割等和子集

2. 目標和

七、完全背包問題

1. 單詞拆分

2. 完全平方數(shù)

3. 組合總和

4. 零錢兌換

5. 零錢兌換2

相關閱讀更多精彩內(nèi)容

友情鏈接更多精彩內(nèi)容

色偷偷精品伊人,欧洲久久精品,欧美综合婷婷骚逼,国产AV主播,国产最新探花在线,九色在线视频一区,伊人大交九欧美,1769亚洲,黄色成人av

一、簡單相加的狀態(tài)轉移

二、取max/min的狀態(tài)轉移

三、嵌套的狀態(tài)轉移

四、連續(xù)子數(shù)組狀態(tài)轉移

五、買賣股票問題

六、0-1背包問題

七、完全背包問題