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

最優(yōu)子結(jié)構(gòu)：問(wèn)題的最優(yōu)解由相關(guān)子問(wèn)題的最優(yōu)解組合而成，而這些子問(wèn)題可以獨(dú)立求解。即一個(gè)問(wèn)題的最優(yōu)解包含其子問(wèn)題的最優(yōu)解。

獨(dú)立求解的理解：如算法導(dǎo)論P(yáng)218中所說(shuō)，要保證分解后得到的子問(wèn)題之間可以獨(dú)立求解，也即同一分解中不同子問(wèn)題所用資源之間沒(méi)有交集

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

動(dòng)態(tài)規(guī)劃與分治法很相似，都是通過(guò)組合子問(wèn)題的解來(lái)解原問(wèn)題，但是分治法的子問(wèn)題之間是不相交的，沒(méi)有公共子子問(wèn)題，比如歸并排序，每一次分割數(shù)組的時(shí)候，子數(shù)組都是不想交的；而動(dòng)態(tài)規(guī)劃在分解子問(wèn)題的時(shí)候，不同的子問(wèn)題擁有公共的子子問(wèn)題，比如爬樓梯問(wèn)題，將n規(guī)模的問(wèn)題分解為了n-1規(guī)模和n-2規(guī)模的問(wèn)題，而n-1規(guī)模的子問(wèn)題中包含n-2規(guī)模的問(wèn)題的解。

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

由于動(dòng)態(tài)規(guī)劃分解得到的子問(wèn)題之間含有公共的子子問(wèn)題，所以如果只是普通的遞歸處理的話，會(huì)進(jìn)行很多重復(fù)的計(jì)算，時(shí)間復(fù)雜度會(huì)成指數(shù)級(jí)增長(zhǎng)，動(dòng)態(tài)規(guī)劃在求解的時(shí)候，會(huì)保存每個(gè)子問(wèn)題的解，這樣當(dāng)再次遇到該子問(wèn)題的時(shí)候直接拿來(lái)使用就可，從而節(jié)省了時(shí)間。

爬樓梯問(wèn)題

鏈接：爬樓梯
經(jīng)典的爬樓梯問(wèn)題：由于一次只能上一個(gè)臺(tái)階或者兩個(gè)臺(tái)階，所以對(duì)于N階樓梯的問(wèn)題可以分為兩個(gè)子問(wèn)題，“(N - 2) + 2”或者“(N - 1) + 1”兩中劃分；而顯然對(duì)于(N - 1)的子問(wèn)題中，包含(N - 2)這個(gè)子問(wèn)題的解。所以如果使用分治法的話，會(huì)產(chǎn)生大量的重復(fù)計(jì)算：

分治法：

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

對(duì)n = 36的情況進(jìn)行測(cè)試，分治法所需的時(shí)間為70ms

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

public int climbStairs(int n) {
    int[] results = new int[n + 1];
    results[1] = 1;
    results[0] = 1;
    for (int i = 2; i <= n; i ++) {
        results[i] = results[i - 1] + results[i - 2];
    }
    return results[n];
}

對(duì)n = 36的情況進(jìn)行測(cè)試，動(dòng)態(tài)規(guī)劃所需的時(shí)間為0ms

上面采取的動(dòng)態(tài)規(guī)劃的策略是：自底向上。也就是，當(dāng)求解一個(gè)問(wèn)題的時(shí)候，其所有子問(wèn)題、子子問(wèn)題等都已經(jīng)被求出、保存了下來(lái)，這樣才能夠當(dāng)再次遇到該子問(wèn)題的時(shí)候直接使用。

上面的遞歸法效率低下的問(wèn)題在于，對(duì)于子問(wèn)題存在重復(fù)計(jì)算的情況，如果我們也能夠保存遇到過(guò)的子問(wèn)題的解，當(dāng)我們分解問(wèn)題的時(shí)候可以查看該子問(wèn)題對(duì)應(yīng)的解是否已經(jīng)有了，如果有的話，我們直接使用，而不是不管不顧地一直遞歸下去，這就引出了動(dòng)態(tài)規(guī)劃另一策略：自頂向下。我們?cè)谶f歸的代碼上修改一下：

class Solution {
    int[] results;
    public int climbStairs(int n) {
        results = new int[n + 1];
        results[0] = 1;
        results[1] = 1;
        return r(n);
    }

    // 方法三：動(dòng)態(tài)規(guī)劃自頂向下  
    public int r(int n) {
        if (results[n] != 0)
            return results[n];
        results[n] = r(n - 1) + r(n - 2);
        return results[n];
    }
}  

自頂向下和自底向上的區(qū)別在于，在求解問(wèn)題的時(shí)候其子問(wèn)題的解不一定已知，但是我們對(duì)同一個(gè)子問(wèn)題只會(huì)求一次；而自底向上法中，我們先求的是子問(wèn)題的解，所以當(dāng)我們求解規(guī)模更大的問(wèn)題的時(shí)候，子問(wèn)題一定已知了。

最小代價(jià)的爬樓梯問(wèn)題

鏈接：使用最小花費(fèi)爬樓梯
我們來(lái)通過(guò)這個(gè)問(wèn)題來(lái)學(xué)習(xí)一下最優(yōu)子結(jié)構(gòu)的分析。

對(duì)于N介臺(tái)階的問(wèn)題，我們?cè)O(shè)情況A為最后一步剛好到第N階，情況B為倒數(shù)第二步到N-1階之后直接一次邁兩步(由于直接登頂，所以這次的代價(jià)為0)到達(dá)第N階。

照這么分析，那么遞推關(guān)系式為P(N) = min{P(N-1), P(N-2)+cost[N]},不同于之前那個(gè)樸素的爬樓梯問(wèn)題，這里的P(N)被分成了兩種情況A和B，也就是說(shuō)每一個(gè)P(N)、P(N-1)...等都是兩種情況中的較優(yōu)的那一個(gè)，這看起來(lái)沒(méi)什么問(wèn)題，但卻有一個(gè)漏洞，那就是P(N)隱含的意義是最終你的腳必須踩到第N階上，但是根據(jù)題意，我們可以一次邁兩步，也就是情況A下我們最終沒(méi)有踩到第N階上，而是就在第N-1階上，這樣一來(lái)就產(chǎn)生了邏輯錯(cuò)誤，因?yàn)镻(N)有可能等于P(N - 1)問(wèn)題的規(guī)模減小了，但是代價(jià)卻一樣？這顯然違背邏輯，因此便失敗了：

class Solution {
    public int minCostClimbingStairs(int[] cost) {
        int[] results = new int[cost.length];
        results[0] = cost[0];
        results[1] = cost[1];
        for (int i = 2; i < results.length; i ++) {
            results[i] = Math.min(results[i - 1], results[i - 2] + cost[i]);
        }

        return results[results.length - 1];
    }
}   

上面的代碼就是根據(jù)其思路來(lái)的，但是是錯(cuò)的。比如cost為[10, 15, 20]顯然最小代價(jià)為15，但是上面的代碼算得的是10，原因在于對(duì)于子問(wèn)題cost[10, 15]其最優(yōu)解為"10"，即情況B，但是原問(wèn)題的最優(yōu)解是"15"即是子問(wèn)題cost[10, 15]的情況A。所以這么分解的話，原問(wèn)題的最優(yōu)解不能用子問(wèn)題的最優(yōu)解合成，動(dòng)態(tài)規(guī)劃便失效了。

正確的分解

上面的錯(cuò)誤的問(wèn)題分解在于原問(wèn)題的最優(yōu)解不能夠用子問(wèn)題的最優(yōu)解合成；而如果我們不去一步到位，我們先只考慮情況A，即每一個(gè)問(wèn)題的最后一步一定恰好在N、N-1、N-2...：

class Solution {
    public int minCostClimbingStairs(int[] cost) {
        int[] results = new int[cost.length];
        results[0] = cost[0];
        results[1] = cost[1];
        for (int i = 2; i < results.length; i ++) {
            results[i] = Math.min(results[i - 1] + cost[i], results[i - 2] + cost[i]);
        }
    } 
}  

這樣的話，results數(shù)組中就保存了所有情況A的最小代價(jià)，那么原問(wèn)題的最優(yōu)解不光有情況A，還有情況B，我們還要思考情況B呢！仔細(xì)分析原問(wèn)題發(fā)現(xiàn)情況B即為N-1下的情況A，所以完整的代碼是：

class Solution {
    public int minCostClimbingStairs(int[] cost) {
        int[] results = new int[cost.length];
        results[0] = cost[0];
        results[1] = cost[1];
        for (int i = 2; i < results.length; i ++) {
            results[i] = Math.min(results[i - 1] + cost[i], results[i - 2] + cost[i]);
        }

        return Math.min(results[cost.length - 1], results[cost.length - 2]);
    }
}  

在返回值上做了手腳。

最大子序和

鏈接：最大子序和
我們?cè)賮?lái)一個(gè)例子來(lái)看看子問(wèn)題的分析。對(duì)于這個(gè)問(wèn)題，假如我們只是簡(jiǎn)單的將P(N)看做數(shù)組從1到N段的最優(yōu)解，那么對(duì)于子問(wèn)題的最優(yōu)解P(N-1)我們便不能夠得到P(N)因?yàn)榇藭r(shí)P(N)的最優(yōu)解可能會(huì)與P(N-1)有不同的元素。
同樣，假如我們將P(N)看做是在包含第N個(gè)元素情況下的解，那么P(N)與P(N-1)之間的關(guān)系就能夠確認(rèn)為P(N) = max{P(N-1) + nums[N], nums[N]}。這樣的話，原問(wèn)題的解便為從1到N的所有P的最大的一個(gè)：

class Solution {
    public int maxSubArray(int[] nums) {
        int[] results = new int[nums.length];
        if (nums.length == 0)
            return 0;
        results[0] = nums[0];
        int max = results[0];
        for (int i = 1; i < nums.length; i ++) {
            if(results[i - 1] >= 0)
                results[i] = nums[i] + results[i - 1];
            else
                results[i] = nums[i];
            max = Math.max(results[i], max);
        }
        return max;
    }
}

實(shí)戰(zhàn)演練

動(dòng)態(tài)規(guī)劃的重點(diǎn)和難點(diǎn)在于對(duì)子問(wèn)題的定義，有些題目中，題干所問(wèn)并不能直接作為子問(wèn)題的定義或者很難去將它進(jìn)行分解。

1. 動(dòng)態(tài)規(guī)劃與數(shù)組

對(duì)于動(dòng)態(tài)規(guī)劃背景下的數(shù)組的某些問(wèn)題，我們通常是將數(shù)組的從第一個(gè)元素開始的、連續(xù)的子數(shù)組作為子問(wèn)題規(guī)模的指標(biāo)，即通常是dp[i]代表數(shù)組從1到i這個(gè)子數(shù)組

例1:最大子序和該題目中，我們將dp[i]定義為從數(shù)組的第1到第i這個(gè)連續(xù)子數(shù)組的最大和(PS:最大和必須包含數(shù)組的第i個(gè)元素)。這樣一來(lái)，狀態(tài)轉(zhuǎn)移方程為

dp[i] = max{dp[i - 1] + nums[i], nums[i]}  

這樣一來(lái)，問(wèn)題的答案就是max{dp[i]}

例2：乘積最大子序列該題目中，我們依舊將dp[i]定義為[0...i]這個(gè)連續(xù)的子數(shù)組的最大乘積的話，我們把子問(wèn)題的解向后應(yīng)用的時(shí)候就會(huì)發(fā)生問(wèn)題，如果nums[i]是一個(gè)負(fù)數(shù)的話，那么dp[i - 1]如果是正的，那么與nums[i]相乘會(huì)變?yōu)樽钚〉?，此時(shí)如果我們把狀態(tài)轉(zhuǎn)移方程依然寫成：

dp[i] = max{dp[i - 1] + nums[i], nums[i]}   

那么以[2, -2, -3]為例，dp[3]理應(yīng)為12，但由于dp[2] = -2,此時(shí)dp[3]成為了6.那么宣告我們dp[i]的定義失敗了。

本例題的核心是正負(fù)數(shù)的變化，一個(gè)負(fù)數(shù)再乘上一個(gè)負(fù)數(shù)之后可能變?yōu)槌朔e最大的了，一個(gè)原本是子問(wèn)題的最大乘積，乘上一個(gè)負(fù)數(shù)之后可能變成了乘積最小的了。正是這種特點(diǎn)，我們需要將最大和最小都保存起來(lái)，因?yàn)樗麄兊牡匚豢赡軙?huì)發(fā)生多次互換

if (a < 0) {
    min[i] = max[i - 1] == 0 ? a : max[i - 1] * a;
    max[i] = min[i - 1] * a;
 } else if (a > 0){
    min[i] = a * min[i - 1];
    max[i] = max[i - 1] == 0 ? a : max[i - 1] * a;
 } else {
    max[i] = 0;
    min[i] = 0;
 }      

這樣一來(lái)，問(wèn)題的答案就是max{max[i]}

感悟：同時(shí)這個(gè)例題也給了我們一個(gè)提醒，不是所有的題目都是可以一步到位的，就像這里的min[i]用來(lái)保存最小的數(shù)，起輔助作用的工具在很多題目中都可以看到。我們要敢于突破，敢于否定自己

例3：最長(zhǎng)上升子序列這里我們依舊將dp[i]定義為子數(shù)組[i...i]中包含nums[i]元素的最長(zhǎng)上升子序列。但此時(shí)子問(wèn)題的最優(yōu)解往后利用的形式發(fā)生了變化：

dp[i] = max{dp[j] + i}(j < i, nums[j] < nums[i])  

這樣一來(lái)，問(wèn)題的答案就是max{dp[i]}

例4：最長(zhǎng)重復(fù)子數(shù)組這里由于涉及到兩個(gè)數(shù)組，所以肯定是要使用dp[i][j]這種形式了，我們嘗試吧其定義為數(shù)組A中[0...i]與B中[0...j]中包含A[i]與B[j]最長(zhǎng)公共子數(shù)組的長(zhǎng)度，那么我們的狀態(tài)轉(zhuǎn)移方程就為：

dp[i][j] = dp[i - 1][j - 1] + i  (A[i] == B[j])  
dp[i][j] = 0                     (A[i] != B[j])  

那么問(wèn)題的答案是max{dp[i][j]}