經(jīng)典算法——?jiǎng)討B(tài)規(guī)劃

姓名：譚旭東 學(xué)號：19011210016

前言

  1. 動(dòng)態(tài)規(guī)劃是什么遵倦？

  • 動(dòng)態(tài)規(guī)劃（dynamic programming）是運(yùn)籌學(xué)的一個(gè)分支，是求解決策過程（decision process）最優(yōu)化的數(shù)學(xué)方法。

  • 動(dòng)態(tài)規(guī)劃一般可分為線性動(dòng)規(guī)秽荤，區(qū)域動(dòng)規(guī)爬早，樹形動(dòng)規(guī)，背包動(dòng)規(guī)四類臣樱。

  • 動(dòng)態(tài)規(guī)劃算法通常用于求解具有某種最優(yōu)性質(zhì)的問題。在這類問題中腮考，可能會(huì)有許多可行解雇毫。每一個(gè)解都對應(yīng)于一個(gè)值，我們希望找到具有最優(yōu)值的解踩蔚。

  • 動(dòng)態(tài)規(guī)劃算法與分治法類似棚放，其基本思想也是將待求解問題分解成若干個(gè)子問題，先求解子問題馅闽，然后從這些子問題的解得到原問題的解飘蚯。

  1. 如何學(xué)習(xí)動(dòng)態(tài)規(guī)劃？
  • 多刷題福也，掌握該算法的整體思路
  • 在接下來的內(nèi)容中局骤，我將通過不同的【轉(zhuǎn)移方程】將動(dòng)態(tài)規(guī)劃的題目進(jìn)行分類，讓我們對不同類型的題目有更好的認(rèn)識

一暴凑、簡單相加的狀態(tài)轉(zhuǎn)移

這類動(dòng)態(tài)規(guī)劃屬于比較簡單的情況峦甩，因?yàn)檗D(zhuǎn)移方程可以簡單的直接得到

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

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

  • 題目出處：509. 斐波那契數(shù)
  • 轉(zhuǎn)移方程：【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 個(gè)泰波那契數(shù)

直接上狀態(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. 爬樓梯
  • 轉(zhuǎn)移方程：【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)轉(zhuǎn)移

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

1. 最小花費(fèi)爬樓梯

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

只需要前兩個(gè)狀態(tài)诫欠，所以還是可以狀態(tài)壓縮（注釋掉的是沒進(jìn)行狀態(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. 打家劫舍
  • 轉(zhuǎn)移方程：【dp[i] = max{dp[i-2] + nums[i] , dp[i-1]}】
    • 分析：因?yàn)椴荒苓B著搶劫狮腿，所以可以【搶第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)轉(zhuǎn)移：和上題一致
  • 初始狀態(tài)：和上題一致

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

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

代碼如下

    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. 刪除并獲得點(diǎn)數(shù)

  • 題目出處：740. 刪除并獲得點(diǎn)數(shù)

  • 狀態(tài)轉(zhuǎn)移：【dp[i] = max{ dp[i-1] , dp[i-2] + count[i]*i }】

    • ① 這里我們將題目轉(zhuǎn)換一種思路法精，相當(dāng)于打家劫舍的進(jìn)階版多律，也就是說我們不能夠選擇相鄰的元素
    • ② 我們需要先得到nums[]數(shù)組中的最大值max，然后將nums[]數(shù)組轉(zhuǎn)換成為count[]數(shù)組搂蜓，統(tǒng)計(jì)每個(gè)數(shù)字出現(xiàn)的次數(shù)（count[]數(shù)組的大小為【max+1】狼荞，從1~max）
    • ③ 然后我們開始狀態(tài)轉(zhuǎn)移過程：可以從i-1狀態(tài)轉(zhuǎn)移到目前狀態(tài)，由于不能夠連著選數(shù)字帮碰，所以這種情況下收益為【dp[i-1]】相味；或者從i-2狀態(tài)轉(zhuǎn)移到目前狀態(tài)，那么目前狀態(tài)是可以選上的殉挽，所以當(dāng)前收益為【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)轉(zhuǎn)移

這種DP的狀態(tài)轉(zhuǎn)移斯碌，會(huì)和之前的所有狀態(tài)有關(guān)一死，不可進(jìn)行狀態(tài)壓縮

1. 跳躍游戲2

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

動(dòng)態(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];
    }

其實(shí)該題目還能用BFS去做瘩绒，不斷對節(jié)點(diǎn)松弛猴抹，有點(diǎn)類似于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) {       // 判斷能否到達(dá)
                    if (d[cur] + 1 < d[i]) {    // 是否松弛成功锁荔，成功才入隊(duì)
                        d[i] = d[cur] + 1;
                        queue.add(i);
                    }
                }
            }
        }
        return d[0];
    }

四蟀给、連續(xù)子數(shù)組狀態(tài)轉(zhuǎn)移

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

1. 最大子序和

  • 題目出處：53. 最大子序和

  • 狀態(tài)轉(zhuǎn)移：

    • ① 設(shè)置一個(gè)sum值跋理，作為我們目前的子數(shù)組和
    • ② 遍歷數(shù)組择克，我們需要求的是最大值，那么我們可以很簡單的分析出前普，最大子數(shù)組肯定不是以負(fù)數(shù)開頭或者結(jié)尾的（除非只有負(fù)數(shù)）
    • ③ 再進(jìn)一步推導(dǎo)肚邢，如果前置的某個(gè)子數(shù)組為負(fù)數(shù)，我們可以將它合并拭卿，那么它對我們接下來需要尋找的最大值是沒有一點(diǎn)正面的幫助的骡湖，需要舍棄掉，繼續(xù)從當(dāng)前位置開始往下找
    • ④ 也就是說峻厚，如果【sum <= 0】响蕴，那么我們從當(dāng)前位置往下找即【sum = nums[i]】
    • ⑤ 如果【sum > 0】，那么不管【nums[i]】是正還是負(fù)惠桃，我們都可以把它加到我們的子數(shù)組中去
    • ⑥ 為什么負(fù)數(shù)還要加進(jìn)去浦夷？是因?yàn)榭赡艹霈F(xiàn)一個(gè)很小的負(fù)數(shù)，但是前面的正數(shù)卻很大的情況辜王，如[100,-1,100]军拟；如果遇到負(fù)數(shù)我們就重新開始的話，是有可能出現(xiàn)撿了芝麻丟了西瓜的情況的
    • ⑦ 如果前面的正數(shù)很小誓禁，而負(fù)數(shù)卻很大的話懈息，如[-100,1,1]；那么這種情況我們通過④就能夠切斷掉前面的很大的負(fù)數(shù)

要用語言表達(dá)思路摹恰，實(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ù)組的最大和

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

  • （1）最大和子數(shù)組出現(xiàn)在中間：
    • ① 這種情況姑宽，包含了首尾都不選（首尾都為負(fù)），或者首尾只選一個(gè)的情況（首尾其中一個(gè)為負(fù)）
    • ② 如果全都是正數(shù)闺阱，那么這種情況還包含了首尾都選的情況
    • ③ 我們可以直接通過上一題的思路炮车，求出這種情況下的最大值max
  • （2）最大子數(shù)組和出現(xiàn)在兩端：
    • ① 這種情況的意思是，最大子數(shù)組同時(shí)包含了首尾元素酣溃，還可能往數(shù)組中間延申
    • ② 假設(shè)整個(gè)數(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ù)組

  • 轉(zhuǎn)移方程：【preMax = max{preMax * nums[i]熙兔，preMin * nums[i]}】悲伶，【preMin = min{preMax * nums[i]，preMin * nums[i]}】

    • ① 由于數(shù)組中的元素有正有負(fù)住涉，負(fù)數(shù)的存在可能會(huì)導(dǎo)致最大值max變最小值min麸锉，最小值min變最大值
    • ② 所以在尋找子序列的過程中，維護(hù)最大值preMax和最小值preMin舆声，表示前綴最大/最小值
    • ③ 還需要考慮一種情況即【nums[i] = 0】淮椰，后面的乘積都為0了，需要從下一個(gè)數(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++) {


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

            /**
             * 是0的情況主穗，會(huì)從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. 最佳觀光組合

  • 轉(zhuǎn)移方程：

    • ① 乘積要為正數(shù)毙芜，那么同上一題一樣忽媒，根據(jù)nums[i]的不同情況分類，我們需要維護(hù)兩個(gè)數(shù)組postive[i]和negative[i]腋粥，分別表示以nums[i]結(jié)尾的子數(shù)組晦雨，前面連續(xù)最長的正數(shù)/負(fù)數(shù)乘積為多少
    • ② 如果【nums[i] = 0】，那么子數(shù)組需要從下一個(gè)開始進(jìn)行計(jì)算隘冲，即【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時(shí)勋锤，將positive[0]置1
    • nums[0]小于0時(shí)痘番，將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)轉(zhuǎn)移：觀光得分：【values[i] + values[j] + i - j】

    • ① 將上述得分拆分成為兩個(gè)部分伊履，對于j位置來說，我們只需要知道前置最大的【values[i] + i】即可
    • ② 通過記錄max{values[i] + i}扣唱，然后遍歷數(shù)組藕坯，我們可以只進(jìn)行一次遍歷就求得結(jié)果

  • 初始狀態(tài)：【maxVi = values[0] + 0】

其實(shí)這題的總體思路就是在遍歷過程中維護(hù)一個(gè)最大值
代碼如下：

    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;
    }

五、 買賣股票問題

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

1. 買賣股票的最佳時(shí)機(jī)

  • 狀態(tài)轉(zhuǎn)移：維護(hù)二維數(shù)組dp[prices.length][2]
    • ① 第一層狀態(tài)i表示到第i天能夠獲得的最大收益
    • ② 第二層狀態(tài)標(biāo)識該天股票的持有情況曲聂，0表示未持有霹购，1表示已持有
    • ③ 當(dāng)前未買入狀態(tài)【dp[i][0]】可以由兩種狀態(tài)轉(zhuǎn)移而來，取兩者最大值
      • 前一天也未持有：【dp[i-1][0]】
      • 前一天已經(jīng)持有朋腋，今天賣出：【dp[i-1][1] + price[i]】
    • ④ 當(dāng)前買入狀態(tài)【dp[i][1]】可以由兩種狀態(tài)轉(zhuǎn)移而來
      • 前一天已經(jīng)持有：【dp[i-1][1]】
      • 前一天未持有齐疙，今天買入：【dp[i-1][0] - price[i]】（需要更改）
      • 注意：<font color=red>這里由于我們只能單次買入賣出股票，所以買入股票這個(gè)操作是無前效性的旭咽，我們需要更改最后一種狀態(tài)為【-price[i]】</font>
  • 初始狀態(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. 買賣股票的最佳時(shí)機(jī)2

  • 題目出處：122. 買賣股票的最佳時(shí)機(jī) II

  • 狀態(tài)轉(zhuǎn)移：一次只能持有一支股票贞奋，可以多次買賣

    • 上一題已經(jīng)分析得到這個(gè)的轉(zhuǎn)移狀態(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. 最佳買賣股票時(shí)機(jī)含冷凍期

  • 題目出處：309. 最佳買賣股票時(shí)機(jī)含冷凍期

  • 狀態(tài)轉(zhuǎn)移：加入冷凍期，時(shí)長為1天穷绵，也就是說前一天賣出股票轿塔，后一天無法再買入；一次最多持有一支股票仲墨，可以多次買入賣出

    • ① 維護(hù)轉(zhuǎn)移數(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. 買賣股票的最佳時(shí)機(jī)含手續(xù)費(fèi)

  • 題目出處：714. 買賣股票的最佳時(shí)機(jī)含手續(xù)費(fèi)

  • 轉(zhuǎn)移方程：一次最多購買一支股票逸邦，可以多次買入賣出汰翠；每次交易（買入+賣出）都需要支付一定的手續(xù)費(fèi)，其實(shí)也可以理解為賣出要收錢

    • ① 正常轉(zhuǎn)移昭雌，加上手續(xù)費(fèi)即可
    • ② 【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]总放，價(jià)值為 v[i]呈宇。在總重量不超過背包承載上限 W 的情況下，能夠裝入背包的最大價(jià)值是多少局雄？
    • <font color=red>如果是 01 背包甥啄，即數(shù)組中的元素不可重復(fù)使用，外循環(huán)遍歷 arrs炬搭，內(nèi)循環(huán)遍歷 target蜈漓，且內(nèi)循環(huán)倒序</font> （因?yàn)檫@里nums中一個(gè)元素只能用一次穆桂，循環(huán)過了就相當(dāng)于取用過了，不再選了）

1. 分割等和子集

  • 題目出處：416. 分割等和子集

  • 思路：只要找到一個(gè)子集融虽，其和剛好為sum/2即可

    • ① 我們維護(hù)一個(gè)【dp[n+1]】數(shù)組享完，表示從0~n的數(shù)是否可以由nums數(shù)組中的數(shù)組成（這里n=sum/2）
    • ② 外層循環(huán)nums，嵌套內(nèi)循環(huán)倒序遍歷dp[i]有额，在nums中找能夠組成i的集合是否存在般又；也就說說我們一個(gè)一個(gè)數(shù)取出來，然后看這個(gè)數(shù)在范圍 [0-target]內(nèi)巍佑，能和前面已存在的結(jié)果構(gòu)成什么新的結(jié)果茴迁。
    • ③ 【dp[i] = dp[i] || dp[i - num]】，之所以要或上一個(gè)dp[i]萤衰，是因?yàn)?strong>結(jié)果具有前效性堕义，也就是說如果早就拼湊出來了這個(gè)子集，要覆蓋后面的結(jié)果使其為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. 目標(biāo)和

  • 題目出處：494. 目標(biāo)和

    • 題目的不同之處在于：選擇數(shù)字的時(shí)候可以進(jìn)行加或者減腻菇，所以我們維護(hù)的數(shù)組長度需要大于target了胳螟，至少得是數(shù)組和【sum】

  • 思路1：我們想辦法把這一題轉(zhuǎn)換為上一題的思路，分析一下有什么不同

    • ① 首先筹吐，所有的數(shù)字都一定要用上一次糖耸，去構(gòu)建目標(biāo)和
    • ② 其次，使用該數(shù)字的時(shí)候可以選擇其前面的符號為正或者負(fù)
    • ③ 我們假設(shè)【target = x - y】丘薛，即x為正數(shù)部分總和嘉竟，y為負(fù)數(shù)部分總和
    • ④ 同時(shí)可以得到【sum = x + y】，也就是整體總和
    • ⑤ 【（target + sum）/2 = x】洋侨，<font color=red>也就是說我們只要在數(shù)組中找到一個(gè)子數(shù)組舍扰，其和為x，構(gòu)成正數(shù)部分希坚，那么剩下的和就為y边苹，構(gòu)成負(fù)數(shù)部分</font>
    • ⑥ 經(jīng)過上述分析，我們將target轉(zhuǎn)換為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;                      // 目標(biāo)和為0个束，可以不選，故總共有一種方案

        for (int num : nums) {
            for (int i = x; i >= num; --i) {
                dp[i] += dp[i - num];
            }
        }
        return dp[x];
    }
  • 思路2：當(dāng)然還有一種做法聊疲，即擴(kuò)大范圍進(jìn)行統(tǒng)計(jì)[-sum茬底，sum]，然后每次狀態(tài)轉(zhuǎn)移時(shí)加上正負(fù)兩種情況
    • ① 維護(hù)二維數(shù)組dp[i][j]获洲，其中i表示只考慮前i個(gè)數(shù)數(shù)字（數(shù)字需要全部用完）阱表，j表示能夠構(gòu)成結(jié)果為j的方案數(shù)量
    • ② 其中i的范圍為[0，len+1]，j的范圍為[-sum最爬，sum]
    • ③ 由于是0-1背包問題涉馁，所以外層循環(huán)取num，內(nèi)層循環(huán)更新方案數(shù)量烂叔，需要同時(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表示使用了前幾個(gè)數(shù)組num
        // j表示能夠構(gòu)成的結(jié)果谨胞，范圍為-sum到sum固歪，下面使用時(shí)需要加入偏移量
        int[][] dp = new int[len + 1][sum * 2 + 1];
        dp[0][sum] = 1;     // 使用0個(gè)元素構(gòu)成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ù)都用上，能構(gòu)成target的方案數(shù)量
        return dp[len][target + sum];
    }

七牢裳、完全背包問題

基本概念：

  • 完全背包與 01 背包不同就是每種物品可以有無限多個(gè)：一共有 N 種物品逢防，每種物品有無限多個(gè)，第 i（i 從 1 開始）種物品的重量為 w[i]蒲讯，價(jià)值為 v[i]忘朝。在總重量不超過背包承載上限 W 的情況下，能夠裝入背包的最大價(jià)值是多少判帮？
  • 一般就是要我們在arr[]數(shù)組中找出能夠組成target的組合
    • （1）如果是完全背包局嘁，即數(shù)組中的元素可重復(fù)使用并且不考慮元素之間順序，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. 單詞拆分

  • 思路：判斷一個(gè)字符串s是否能夠拆分成為一個(gè)或者多個(gè)在字典wordDict中出現(xiàn)的單詞

    • ① 維護(hù)一個(gè)數(shù)組dp[i]抗楔，表示字符串i以及其之前的字串能否由wordDict中的串組成棋凳，i的范圍為[0，s.len]
    • ② 外層循環(huán)遍歷目標(biāo)字符串s连躏，內(nèi)層循環(huán)遍歷字典wordDict（字典中元素可重復(fù)使用）
    • ③ dp[i] = dp[i-len] || dp[i]（這里的len為字典中某個(gè)字符的長度）
    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ù)

  • 思路：將題目轉(zhuǎn)換成為從數(shù)組nums[1剩岳，sqrt(n)]中，選出平方數(shù)能夠組成target的組合入热，并且使組合中數(shù)量個(gè)數(shù)最小

    • ① 維護(hù)一個(gè)dp[i]數(shù)組拍棕，i組成的結(jié)果，dp[i]表示組成結(jié)果i需要的最少數(shù)量
    • ② 數(shù)組nums中的元素是可以重復(fù)使用的才顿，所以為完全背包問題
    • ③ 外層循環(huán)遍歷nums取數(shù)莫湘，內(nèi)層循環(huán)找不同的組合方案（從0-target中任意一個(gè)數(shù)轉(zhuǎn)換到target都可以使方案+1）
    • ④ 初始狀態(tài)dp[0] = 0，表示結(jié)果為0的完全平方數(shù)和組合為0個(gè)郑气，其余都為無窮大（方便取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ù)字可以重復(fù)選取，不同的順序組成的組合是不一樣的

    • ① 維護(hù)數(shù)組dp[i]尾组，表示組成和為i的組合數(shù)量
    • ② 在這個(gè)題目中忙芒，由于不同的選擇順序認(rèn)作不同的結(jié)果示弓，所以我們在外層遍歷dp[]數(shù)組，在內(nèi)層遍歷nums數(shù)組呵萨，這樣的話可以表示不同的組合順序
    • ③ 【dp[i] = dp[i] + dp[i-num]】

4. 零錢兌換

  • 題目出處：322. 零錢兌換

  • 思路：每種硬幣是無限的奏属，需要返回能夠構(gòu)成指定amount額度的最小硬幣數(shù)量

    • ① 維護(hù)dp[i]數(shù)組，表示構(gòu)成額度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，可能需要考慮反轉(zhuǎn)問題忱嘹，所以隨便找一個(gè)大數(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

  • 思路：這題和上一題不一樣之處在于嘱腥，在本題目中重復(fù)的組合是需要排除掉的

    • ① 維護(hù)dp[i]數(shù)組，表示構(gòu)成額度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

?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請聯(lián)系作者
  • 人面猴
    序言：七十年代末分苇，一起剝皮案震驚了整個(gè)濱河市，隨后出現(xiàn)的幾起案子屁桑，更是在濱河造成了極大的恐慌医寿，老刑警劉巖，帶你破解...
    沈念sama閱讀 217,657評論 6贊 505
  • 死咒
    序言：濱河連續(xù)發(fā)生了三起死亡事件掏颊，死亡現(xiàn)場離奇詭異糟红，居然都是意外死亡，警方通過查閱死者的電腦和手機(jī)乌叶，發(fā)現(xiàn)死者居然都...
    沈念sama閱讀 92,889評論 3贊 394
  • 救了他兩次的神仙讓他今天三更去死
    文/潘曉璐 我一進(jìn)店門盆偿，熙熙樓的掌柜王于貴愁眉苦臉地迎上來，“玉大人准浴，你說我怎么就攤上這事事扭。” “怎么了乐横？”我有些...
    開封第一講書人閱讀 164,057評論 0贊 354
  • 道士緝兇錄：失蹤的賣姜人
    文/不壞的土叔 我叫張陵求橄，是天一觀的道長。 經(jīng)常有香客問我葡公，道長罐农，這世上最難降的妖魔是什么？ 我笑而不...
    開封第一講書人閱讀 58,509評論 1贊 293
  • ?港島之戀（遺憾婚禮）
    正文 為了忘掉前任催什，我火速辦了婚禮涵亏，結(jié)果婚禮上，老公的妹妹穿的比我還像新娘。我一直安慰自己气筋，他們只是感情好拆内，可當(dāng)我...
    茶點(diǎn)故事閱讀 67,562評論 6贊 392
  • 惡毒庶女頂嫁案：這布局不是一般人想出來的
    文/花漫 我一把揭開白布。 她就那樣靜靜地躺著宠默，像睡著了一般麸恍。 火紅的嫁衣襯著肌膚如雪。 梳的紋絲不亂的頭發(fā)上搀矫，一...
    開封第一講書人閱讀 51,443評論 1贊 302
  • 城市分裂傳說
    那天抹沪，我揣著相機(jī)與錄音，去河邊找鬼艾君。 笑死采够，一個(gè)胖子當(dāng)著我的面吹牛肄方，可吹牛的內(nèi)容都是我干的冰垄。 我是一名探鬼主播，決...
    沈念sama閱讀 40,251評論 3贊 418
  • 雙鴛鴦連環(huán)套：你想象不到人心有多黑
    文/蒼蘭香墨 我猛地睜開眼权她，長吁一口氣：“原來是場噩夢啊……” “哼虹茶！你這毒婦竟也來了？” 一聲冷哼從身側(cè)響起隅要，我...
    開封第一講書人閱讀 39,129評論 0贊 276
  • 萬榮殺人案實(shí)錄
    序言：老撾萬榮一對情侶失蹤蝴罪，失蹤者是張志新（化名）和其女友劉穎，沒想到半個(gè)月后步清，有當(dāng)?shù)厝嗽跇淞掷锇l(fā)現(xiàn)了一具尸體要门，經(jīng)...
    沈念sama閱讀 45,561評論 1贊 314
  • ?護(hù)林員之死
    正文 獨(dú)居荒郊野嶺守林人離奇死亡，尸身上長有42處帶血的膿包…… 初始之章·張勛 以下內(nèi)容為張勛視角 年9月15日...
    茶點(diǎn)故事閱讀 37,779評論 3贊 335
  • ?白月光啟示錄
    正文 我和宋清朗相戀三年廓啊，在試婚紗的時(shí)候發(fā)現(xiàn)自己被綠了欢搜。 大學(xué)時(shí)的朋友給我發(fā)了我未婚夫和他白月光在一起吃飯的照片。...
    茶點(diǎn)故事閱讀 39,902評論 1贊 348
  • 活死人
    序言：一個(gè)原本活蹦亂跳的男人離奇死亡谴轮，死狀恐怖炒瘟，靈堂內(nèi)的尸體忽然破棺而出，到底是詐尸還是另有隱情第步，我是刑警寧澤疮装，帶...
    沈念sama閱讀 35,621評論 5贊 345
  • ?日本核電站爆炸內(nèi)幕
    正文 年R本政府宣布，位于F島的核電站粘都，受9級特大地震影響廓推，放射性物質(zhì)發(fā)生泄漏。R本人自食惡果不足惜翩隧，卻給世界環(huán)境...
    茶點(diǎn)故事閱讀 41,220評論 3贊 328
  • 男人毒藥：我在死后第九天來索命
    文/蒙蒙 一樊展、第九天 我趴在偏房一處隱蔽的房頂上張望。 院中可真熱鬧，春花似錦滚局、人聲如沸居暖。這莊子的主人今日做“春日...
    開封第一講書人閱讀 31,838評論 0贊 22
  • 一樁弒父案藤肢，背后竟有這般陰謀
    文/蒼蘭香墨 我抬頭看了看天上的太陽太闺。三九已至，卻和暖如春嘁圈，著一層夾襖步出監(jiān)牢的瞬間省骂，已是汗流浹背。 一陣腳步聲響...
    開封第一講書人閱讀 32,971評論 1贊 269
  • 情欲美人皮
    我被黑心中介騙來泰國打工最住， 沒想到剛下飛機(jī)就差點(diǎn)兒被人妖公主榨干…… 1. 我叫王不留钞澳，地道東北人。 一個(gè)月前我還...
    沈念sama閱讀 48,025評論 2贊 370
  • 代替公主和親
    正文 我出身青樓涨缚，卻偏偏與公主長得像轧粟，于是被迫代替她去往敵國和親。 傳聞我的和親對象是個(gè)殘疾皇子脓魏，可洞房花燭夜當(dāng)晚...
    茶點(diǎn)故事閱讀 44,843評論 2贊 354

推薦閱讀更多精彩內(nèi)容