大廠算法面試之leetcode精講3.動(dòng)態(tài)規(guī)劃

視頻教程（高效學(xué)習(xí)）:點(diǎn)擊學(xué)習(xí)

目錄：

1.開篇介紹

2.時(shí)間空間復(fù)雜度

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

4.貪心

5.二分查找

6.深度優(yōu)先&廣度優(yōu)先

7.雙指針

8.滑動(dòng)窗口

9.位運(yùn)算

10.遞歸&分治

11剪枝&回溯

12.堆

13.單調(diào)棧

14.排序算法

15.鏈表

16.set&map

17.棧

18.隊(duì)列

19.數(shù)組

20.字符串

21.樹

22.字典樹

23.并查集

24.其他類型題

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

動(dòng)態(tài)規(guī)劃，英文：Dynamic Programming，簡(jiǎn)稱DP，將問題分解為互相重疊的子問題，通過反復(fù)求解子問題來解決原問題就是動(dòng)態(tài)規(guī)劃，如果某一問題有很多重疊子問題，使用動(dòng)態(tài)規(guī)劃來解是比較有效的。

求解動(dòng)態(tài)規(guī)劃的核心問題是窮舉，但是這類問題窮舉有點(diǎn)特別，因?yàn)檫@類問題存在「重疊子問題」，如果暴力窮舉的話效率會(huì)極其低下。動(dòng)態(tài)規(guī)劃問題一定會(huì)具備「最優(yōu)子結(jié)構(gòu)」，才能通過子問題的最值得到原問題的最值。另外，雖然動(dòng)態(tài)規(guī)劃的核心思想就是窮舉求最值，但是問題可以千變?nèi)f化，窮舉所有可行解其實(shí)并不是一件容易的事，只有列出正確的「狀態(tài)轉(zhuǎn)移方程」才能正確地窮舉。重疊子問題、最優(yōu)子結(jié)構(gòu)、狀態(tài)轉(zhuǎn)移方程就是動(dòng)態(tài)規(guī)劃三要素

動(dòng)態(tài)規(guī)劃和其他算法的區(qū)別

  1. 動(dòng)態(tài)規(guī)劃和分治的區(qū)別：動(dòng)態(tài)規(guī)劃和分治都有最優(yōu)子結(jié)構(gòu) ，但是分治的子問題不重疊
  2. 動(dòng)態(tài)規(guī)劃和貪心的區(qū)別：動(dòng)態(tài)規(guī)劃中每一個(gè)狀態(tài)一定是由上一個(gè)狀態(tài)推導(dǎo)出來的，這一點(diǎn)就區(qū)分于貪心，貪心沒有狀態(tài)推導(dǎo)，而是從局部直接選最優(yōu)解，所以它永遠(yuǎn)是局部最優(yōu)，但是全局的解不一定是最優(yōu)的。
  3. 動(dòng)態(tài)規(guī)劃和遞歸的區(qū)別：遞歸和回溯可能存在非常多的重復(fù)計(jì)算，動(dòng)態(tài)規(guī)劃可以用遞歸加記憶化的方式減少不必要的重復(fù)計(jì)算

動(dòng)態(tài)規(guī)劃的解題方法

  • 遞歸+記憶化(自頂向下)
  • 動(dòng)態(tài)規(guī)劃（自底向上）

解動(dòng)態(tài)規(guī)劃題目的步驟

  1. 根據(jù)重疊子問題定義狀態(tài)
  2. 尋找最優(yōu)子結(jié)構(gòu)推導(dǎo)狀態(tài)轉(zhuǎn)移方程
  3. 確定dp初始狀態(tài)
  4. 確定輸出值

斐波那契的動(dòng)態(tài)規(guī)劃的解題思路

動(dòng)畫過大，點(diǎn)擊查看

暴力遞歸
//暴力遞歸復(fù)雜度O(2^n)var fib = function (N) {    if (N == 0) return 0;    if (N == 1) return 1;    return fib(N - 1) + fib(N - 2);};
遞歸 + 記憶化
var fib = function (n) {    const memo = {}; // 對(duì)已算出的結(jié)果進(jìn)行緩存    const helper = (x) => {        if (memo[x]) return memo[x];        if (x == 0) return 0;        if (x == 1) return 1;        memo[x] = fib(x - 1) + fib(x - 2);        return memo[x];    };    return helper(n);};
動(dòng)態(tài)規(guī)劃
const fib = (n) => {    if (n <= 1) return n;    const dp = [0, 1];    for (let i = 2; i <= n; i++) {        //自底向上計(jì)算每個(gè)狀態(tài)        dp[i] = dp[i - 1] + dp[i - 2];    }    return dp[n];};
滾動(dòng)數(shù)組優(yōu)化
const fib = (n) => {    if (n <= 1) return n;    //滾動(dòng)數(shù)組 dp[i]只和dp[i-1]、dp[i-2]相關(guān)，只維護(hù)長(zhǎng)度為2的滾動(dòng)數(shù)組，不斷替換數(shù)組元素    const dp = [0, 1];    let sum = null;    for (let i = 2; i <= n; i++) {        sum = dp[0] + dp[1];        dp[0] = dp[1];        dp[1] = sum;    }    return sum;};
動(dòng)態(tài)規(guī)劃 + 降維，（降維能減少空間復(fù)雜度，但不利于程序的擴(kuò)展）
var fib = function (N) {    if (N <= 1) {        return N;    }    let prev2 = 0;    let prev1 = 1;    let result = 0;    for (let i = 2; i <= N; i++) {        result = prev1 + prev2; //直接用兩個(gè)變量就行        prev2 = prev1;        prev1 = result;    }    return result;};

509. 斐波那契數(shù)（easy）

方法1.動(dòng)態(tài)規(guī)劃
  • 思路：自底而上的動(dòng)態(tài)規(guī)劃
  • 復(fù)雜度分析：時(shí)間復(fù)雜度O(n)，空間復(fù)雜度O(1)

Js:

var fib = function (N) {    if (N <= 1) {        return N;    }    let prev2 = 0;    let prev1 = 1;    let result = 0;    for (let i = 2; i <= N; i++) {        result = prev1 + prev2;        prev2 = prev1;        prev1 = result;    }    return result;};

Java:

class Solution {    public int fib(int n) {        if (n <= 1) {            return n;        }        int prev2 = 0, prev1 = 1, result = 0;        for (int i = 2; i <= n; i++) {            result = prev2 + prev1;            prev2 = prev1;             prev1 = result;         }        return result;    }}

62. 不同路徑 （medium）

方法1.動(dòng)態(tài)規(guī)劃

動(dòng)畫過大，點(diǎn)擊查看

  • 思路:由于在每個(gè)位置只能向下或者向右， 所以每個(gè)坐標(biāo)的路徑和等于上一行相同位置和上一列相同位置不同路徑的總和，狀態(tài)轉(zhuǎn)移方程：f[i][j] = f[i - 1][j] + f[i][j - 1];
  • 復(fù)雜度:時(shí)間復(fù)雜度O(mn)。空間復(fù)雜度O(mn)，優(yōu)化后O(n)

js:

var uniquePaths = function (m, n) {    const f = new Array(m).fill(0).map(() => new Array(n).fill(0)); //初始dp數(shù)組    for (let i = 0; i < m; i++) {        //初始化列        f[i][0] = 1;    }    for (let j = 0; j < n; j++) {        //初始化行        f[0][j] = 1;    }    for (let i = 1; i < m; i++) {        for (let j = 1; j < n; j++) {            f[i][j] = f[i - 1][j] + f[i][j - 1];        }    }    return f[m - 1][n - 1];};//狀態(tài)壓縮var uniquePaths = function (m, n) {    let cur = new Array(n).fill(1);    for (let i = 1; i < m; i++) {        for (let r = 1; r < n; r++) {            cur[r] = cur[r - 1] + cur[r];        }    }    return cur[n - 1];};

Java:

class Solution {    public int uniquePaths(int m, int n) {        int[][] f = new int[m][n];        for (int i = 0; i < m; ++i) {            f[i][0] = 1;        }        for (int j = 0; j < n; ++j) {            f[0][j] = 1;        }        for (int i = 1; i < m; ++i) {            for (int j = 1; j < n; ++j) {                f[i][j] = f[i - 1][j] + f[i][j - 1];            }        }        return f[m - 1][n - 1];    }}//狀態(tài)壓縮class Solution {    public int uniquePaths(int m, int n) {        int[] cur = new int[n];        Arrays.fill(cur,1);        for (int i = 1; i < m;i++){            for (int j = 1; j < n; j++){                cur[j] += cur[j-1] ;            }        }        return cur[n-1];    }}

63. 不同路徑 II（medium）

方法1.動(dòng)態(tài)規(guī)劃
  • 思路：和62題一樣，區(qū)別就是遇到障礙直接返回0
  • 復(fù)雜度：時(shí)間復(fù)雜度O(mn)，空間復(fù)雜度O(mn)，狀態(tài)壓縮之后是o(n)

Js:

var uniquePathsWithObstacles = function (obstacleGrid) {    const m = obstacleGrid.length;    const n = obstacleGrid[0].length;    const dp = Array(m)        .fill()        .map((item) => Array(n).fill(0)); //初始dp數(shù)組    for (let i = 0; i < m && obstacleGrid[i][0] === 0; ++i) {        //初始列        dp[i][0] = 1;    }    for (let i = 0; i < n && obstacleGrid[0][i] === 0; ++i) {        //初始行        dp[0][i] = 1;    }    for (let i = 1; i < m; ++i) {        for (let j = 1; j < n; ++j) {            //遇到障礙直接返回0            dp[i][j] = obstacleGrid[i][j] === 1 ? 0 : dp[i - 1][j] + dp[i][j - 1];        }    }    return dp[m - 1][n - 1];};//狀態(tài)壓縮var uniquePathsWithObstacles = function (obstacleGrid) {    let m = obstacleGrid.length;    let n = obstacleGrid[0].length;    let dp = Array(n).fill(0); //用0填充，因?yàn)楝F(xiàn)在有障礙物，當(dāng)前dp數(shù)組元素的值還和obstacleGrid[i][j]有關(guān)    dp[0] = 1; //第一列 暫時(shí)用1填充    for (let i = 0; i < m; i++) {        for (let j = 0; j < n; j++) {            if (obstacleGrid[i][j] == 1) {                //注意條件，遇到障礙物dp[j]就變成0，這里包含了第一列的情況                dp[j] = 0;            } else if (j > 0) {                //只有當(dāng)j>0 不是第一列了才能取到j(luò) - 1                dp[j] += dp[j - 1];            }        }    }    return dp[n - 1];};

Java:

class Solution {    public int uniquePathsWithObstacles(int[][] obstacleGrid) {        int n = obstacleGrid.length, m = obstacleGrid[0].length;        int[] dp = new int[m];        dp[0] = obstacleGrid[0][0] == 0 ? 1 : 0;        for (int i = 0; i < n; ++i) {            for (int j = 0; j < m; ++j) {                if (obstacleGrid[i][j] == 1) {                    dp[j] = 0;                    continue;                }                if (j - 1 >= 0 && obstacleGrid[i][j - 1] == 0) {                    dp[j] += dp[j - 1];                }            }        }        return dp[m - 1];    }}

70. 爬樓梯 （medium）

方法1.動(dòng)態(tài)規(guī)劃

  • 思路：因?yàn)槊看慰梢耘?1 或 2 個(gè)臺(tái)階，所以到第n階臺(tái)階可以從第n-2或n-1上來，其實(shí)就是斐波那契的dp方程
  • 復(fù)雜度分析：時(shí)間復(fù)雜度O(n)，空間復(fù)雜度O(1)

Js:

var climbStairs = function (n) {    const memo = [];    memo[1] = 1;    memo[2] = 2;    for (let i = 3; i <= n; i++) {        memo[i] = memo[i - 2] + memo[i - 1];//所以到第n階臺(tái)階可以從第n-2或n-1上來    }    return memo[n];};//狀態(tài)壓縮var climbStairs = (n) => {    let prev = 1;    let cur = 1;    for (let i = 2; i < n + 1; i++) {        [prev, cur] = [cur, prev + cur]        // const temp = cur;   // 暫存上一次的cur        // cur = prev + cur;   // 當(dāng)前的cur = 上上次cur + 上一次cur        // prev = temp;        // prev 更新為 上一次的cur    }    return cur;}

Java:

class Solution {    public int climbStairs(int n) {        int prev = 1, cur = 1;        for (int i = 2; i < n + 1; i++) {        int temp = cur;        cur = prev + cur;          prev = temp;         }        return cur;    }}

279. 完全平方數(shù) (medium)

方法1:動(dòng)態(tài)規(guī)劃

  • 思路：dp[i] 表示i的完全平方和的最少數(shù)量，dp[i - j * j] + 1表示減去一個(gè)完全平方數(shù)j的完全平方之后的數(shù)量加1就等于dp[i]，只要在dp[i], dp[i - j * j] + 1中尋找一個(gè)較少的就是最后dp[i]的值。

  • 復(fù)雜度：時(shí)間復(fù)雜度O(n* sqrt(n))，n是輸入的整數(shù)，需要循環(huán)n次，每次計(jì)算dp方程的復(fù)雜度sqrt(n)，空間復(fù)雜度O(n)

js：

var numSquares = function (n) {    const dp = [...Array(n)].map((_) => 0); //初始化dp數(shù)組 當(dāng)n為0的時(shí)候    for (let i = 1; i <= n; i++) {        dp[i] = i; // 最壞的情況就是每次+1 比如: dp[3]=1+1+1        for (let j = 1; i - j * j >= 0; j++) {//枚舉前一個(gè)狀態(tài)            dp[i] = Math.min(dp[i], dp[i - j * j] + 1); // 動(dòng)態(tài)轉(zhuǎn)移方程        }    }    return dp[n];};

java：

class Solution {    public int numSquares(int n) {        int[] dp = new int[n];        for (int i = 1; i <= n; i++) {            dp[i] = i;            for (int j = 1; i - j * j >= 0; j++) {                 dp[i] = Math.min(dp[i], dp[i - j * j] + 1);            }        }        return dp[n];    }}

120. 三角形最小路徑和（medium）

方法1.動(dòng)態(tài)規(guī)劃

  • 思路：從三角形最后一層開始向上遍歷，每個(gè)數(shù)字的最小路徑和是它下面兩個(gè)數(shù)字中的較小者加上它本身
  • 復(fù)雜度分析：時(shí)間復(fù)雜度O(n^2)，空間復(fù)雜O(n)

Js:

const minimumTotal = (triangle) => {    const h = triangle.length;    // 初始化dp數(shù)組    const dp = new Array(h);    for (let i = 0; i < h; i++) {        dp[i] = new Array(triangle[i].length);    }    for (let i = h - 1; i >= 0; i--) { //自底而上遍歷        for (let j = 0; j < triangle[i].length; j++) { //同一層的            if (i == h - 1) {  // base case 最底層                dp[i][j] = triangle[i][j];            } else { // 狀態(tài)轉(zhuǎn)移方程，上一層由它下面一層計(jì)算出                dp[i][j] = Math.min(dp[i + 1][j], dp[i + 1][j + 1]) + triangle[i][j];            }        }    }    return dp[0][0];};//狀態(tài)壓縮const minimumTotal = (triangle) => {    const bottom = triangle[triangle.length - 1];    const dp = new Array(bottom.length);    // base case 是最后一行    for (let i = 0; i < dp.length; i++) {        dp[i] = bottom[i];    }    // 從倒數(shù)第二列開始迭代    for (let i = dp.length - 2; i >= 0; i--) {        for (let j = 0; j < triangle[i].length; j++) {            dp[j] = Math.min(dp[j], dp[j + 1]) + triangle[i][j];        }    }    return dp[0];};

Java:

class Solution {    public int minimumTotal(List> triangle) {        int n = triangle.size();        int [] dp = new int [n];        for(int i = 0 ; i < n ; i++){            dp[i] = triangle.get(n-1).get(i);        }        for(int i = n-2 ; i >= 0 ; i--){            for(int j = 0 ; j <= i ; j++){                dp[j] = triangle.get(i).get(j) + Math.min(dp[j] , dp[j+1]);//迭代            }        }        return dp[0];    }}

152. 乘積最大子數(shù)組 （medium）

方法1.動(dòng)態(tài)規(guī)劃

  • 思路：

    1. 狀態(tài)定義：dp[i][0]表示從第 0 項(xiàng)到第 i 項(xiàng)范圍內(nèi)的子數(shù)組的最小乘積，dp[i][1]表示從第 0 項(xiàng)到第 i 項(xiàng)范圍內(nèi)的子數(shù)組的最大乘積

    2. 初始狀態(tài)：dp[0][0]=nums[0], dp[0][1]=nums[0]

    3. 分情況討論:

      • 不和別人乘，就 nums[i]自己
      • num[i] 是負(fù)數(shù)，希望乘上前面的最大積
      • num[i] 是正數(shù)，希望乘上前面的最小積

    4. 狀態(tài)轉(zhuǎn)移方程：

      • dp[i] [0]=min(dp[i?1] [0]?num[i] , dp[i?1] [1] ? num[i], num[i])
      • dp[i] [1]=max(dp[i?1] [0]?num[i] , dp[i?1] [1] ? num[i], num[i])

    5. 狀態(tài)壓縮：dp[i][x]只與dp[i][x]-1，所以只需定義兩個(gè)變量，prevMin = nums[0]，prevMax = nums[0]

    6. 狀態(tài)壓縮之后的方程：

      • prevMin = Math.min(prevMin num[i], prevMax num[i], nums[i])
      • prevMax = Math.max(prevMin num[i], prevMax num[i], nums[i])
  • 復(fù)雜度：時(shí)間復(fù)雜度O(n)，空間復(fù)雜度O(1)

js:

var maxProduct = (nums) => {    let res = nums[0]    let prevMin = nums[0]    let prevMax = nums[0]    let temp1 = 0, temp2 = 0    for (let i = 1; i < nums.length; i++) {        temp1 = prevMin * nums[i]        temp2 = prevMax * nums[i]        prevMin = Math.min(temp1, temp2, nums[i])        prevMax = Math.max(temp1, temp2, nums[i])        res = Math.max(prevMax, res)    }    return res}

Java:

class Solution {    public int maxProduct(int[] nums) {        int res = nums[0], prevMin = nums[0], prevMax = nums[0];        int temp1 = 0, temp2 = 0;        for (int i = 1; i < nums.length; i++) {            temp1 = prevMin * nums[i];            temp2 = prevMax * nums[i];            prevMin = Math.min(Math.min(temp1, temp2), nums[i]);            prevMax = Math.max(Math.max(temp1, temp2), nums[i]);            res = Math.max(prevMax, res);        }        return res;    }}

買賣股票問題

121. 買賣股票的最佳時(shí)機(jī)（easy）限定交易次數(shù) k=1

122. 買賣股票的最佳時(shí)機(jī) II（medium）交易次數(shù)無(wú)限制 k = +infinity

123. 買賣股票的最佳時(shí)機(jī) III (hrad) 限定交易次數(shù) k=2

188. 買賣股票的最佳時(shí)機(jī) IV (hard) 限定交易次數(shù) 最多次數(shù)為 k

309. 最佳買賣股票時(shí)機(jī)含冷凍期(medium) 含有交易冷凍期

714. 買賣股票的最佳時(shí)機(jī)含手續(xù)費(fèi) (medium) 每次交易含手續(xù)費(fèi)

第5，6道題相當(dāng)于在第2道題的基礎(chǔ)上加了冷凍期和手續(xù)費(fèi)的條件。

限制條件
  • 先買入才能賣出
  • 不能同時(shí)參加多筆交易，再次買入時(shí)，需要先賣出
  • k >= 0才能進(jìn)行交易，否則沒有交易次數(shù)
定義操作
  • 買入
  • 賣出
  • 不操作
定義狀態(tài)
  • i: 天數(shù)
  • k: 交易次數(shù)，每次交易包含買入和賣出，這里我們只在買入的時(shí)候需要將 k - 1
  • 0: 不持有股票
  • 1: 持有股票
舉例
dp[i][k][0]//第i天 還可以交易k次 手中沒有股票dp[i][k][1]//第i天 還可以交易k次 手中有股票

最終的最大收益是dp[n - 1][k][0]而不是dp[n - 1][k][1]，因?yàn)樽詈笠惶熨u出肯定比持有收益更高

狀態(tài)轉(zhuǎn)移方程
// 今天沒有持有股票，分為兩種情況// 1. dp[i - 1][k][0]，昨天沒有持有，今天不操作。 // 2. dp[i - 1][k][1] + prices[i] 昨天持有，今天賣出，今天手中就沒有股票了。dp[i][k][0] = Math.max(dp[i - 1][k][0], dp[i - 1][k][1] + prices[i])// 今天持有股票，分為兩種情況：// 1.dp[i - 1][k][1] 昨天持有，今天不操作// 2.dp[i - 1][k - 1][0] - prices[i] 昨天沒有持有，今天買入。dp[i][k][1] = Math.max(dp[i - 1][k][1], dp[i - 1][k - 1][0] - prices[i])//最大利潤(rùn)就是這倆種情況的最大值

121. 買賣股票的最佳時(shí)機(jī)（easy）限定交易次數(shù) k=1

狀態(tài)轉(zhuǎn)移方程

//第i天不持有 由 第i-1天不持有然后不操作 和 第i-1天持有然后賣出 兩種情況的最大值轉(zhuǎn)移過來dp[i][1][0] = Math.max(dp[i - 1][1][0], dp[i - 1][1][1] + prices[i])//第i天持有 由 第i-1天持有然后不操作 和 第i-1天不持有然后買入 兩種情況的最大值轉(zhuǎn)移過來dp[i][1][1] = Math.max(dp[i - 1][1][1], dp[i - 1][0][0] - prices[i])            = Math.max(dp[i - 1][1][1], -prices[i]) // k=0時(shí) 沒有交易次數(shù)，dp[i - 1][0][0] = 0

k是固定值1，不影響結(jié)果，所以可以不用管，簡(jiǎn)化之后如下

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])

完整代碼

//時(shí)間復(fù)雜度O(n) 空間復(fù)雜度O(n)，dp數(shù)組第二維是常數(shù)const maxProfit = function (prices) {    let n = prices.length;    let dp = Array.from(new Array(n), () => new Array(2));    dp[0][0] = 0; //第0天不持有    dp[0][1] = -prices[0]; //第0天持有    for (let i = 1; i < n; 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[n - 1][0];};

狀態(tài)壓縮，dp[i] 只和 dp[i - 1] 有關(guān)，去掉一維

//時(shí)間復(fù)雜度O(n) 空間復(fù)雜度O(1)const maxProfit = function (prices) {    let n = prices.length;    let dp = Array.from(new Array(n), () => new Array(2));    dp[0] = 0;    dp[1] = -prices[0];    for (let i = 1; i < n; i++) {        dp[0] = Math.max(dp[0], dp[1] + prices[i]);        dp[1] = Math.max(dp[1], -prices[i]);    }    return dp[0];};//語(yǔ)意化const maxProfit = function (prices) {    let n = prices.length;    let sell = 0;    let buy = -prices[0];    for (let i = 1; i < n; i++) {        sell = Math.max(sell, buy + prices[i]);        buy = Math.max(buy, -prices[i]);    }    return sell;};

122. 買賣股票的最佳時(shí)機(jī) II（medium）交易次數(shù)無(wú)限制 k = +infinity

狀態(tài)轉(zhuǎn)移方程

//第i天不持有 由 第i-1天不持有然后不操作 和 第i-1天持有然后賣出 兩種情況的最大值轉(zhuǎn)移過來dp[i][k][0] = Math.max(dp[i - 1][k][0], dp[i - 1][k][1] + prices[i])//第i天持有 由 第i-1天持有然后不操作 和 第i-1天不持有然后買入 兩種情況的最大值轉(zhuǎn)移過來dp[i][k][1] = Math.max(dp[i - 1][k][1], dp[i - 1][k - 1][0] - prices[i])

k同樣不影響結(jié)果，簡(jiǎn)化之后如下

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])

完整代碼

const maxProfit = function (prices) {    let n = prices.length;    let dp = Array.from(new Array(n), () => new Array(2));    dp[0][0] = 0; //第0天不持有    dp[0][1] = -prices[0]; //第0天買入 花了prices[0]    for (let i = 1; i < n; 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[n - 1][0];};

狀態(tài)壓縮，同樣dp[i] 只和 dp[i - 1] 有關(guān)，去掉一維

const maxProfit = function (prices) {    let n = prices.length;    let dp = Array.from(new Array(n), () => new Array(2));    dp[0] = 0;    dp[1] = -prices[0];    for (let i = 1; i < n; i++) {        dp[0] = Math.max(dp[0], dp[1] + prices[i]);        dp[1] = Math.max(dp[1], dp[0] - prices[i]);    }    return dp[0];};//語(yǔ)意化const maxProfit = function (prices) {    let n = prices.length;    let sell = 0;    let buy = -prices[0];    for (let i = 1; i < n; i++) {        sell = Math.max(sell, buy + prices[i]);        buy = Math.max(buy, sell - prices[i]);    }    return sell;};

123. 買賣股票的最佳時(shí)機(jī) III (hrad) 限定交易次數(shù) k=2

狀態(tài)轉(zhuǎn)移方程

dp[i][k][0] = Math.max(dp[i - 1][k][0], dp[i - 1][k][1] + prices[i])dp[i][k][1] = Math.max(dp[i - 1][k][1], dp[i - 1][k - 1][0] - prices[i])

k對(duì)結(jié)果有影響 不能舍去，只能對(duì)k進(jìn)行循環(huán)

for (let i = 0; i < n; i++) {  for (let k = maxK; k >= 1; k--) {    dp[i][k][0] = Math.max(dp[i - 1][k][0], dp[i - 1][k][1] + prices[i]);    dp[i][k][1] = Math.max(dp[i - 1][k][1], dp[i - 1][k - 1][0] - prices[i]);  }}//k=2，直接寫出循環(huán)的結(jié)果dp[i][2][0] = Math.max(dp[i - 1][2][0], dp[i - 1][2][1] + prices[i])dp[i][2][1] = Math.max(dp[i - 1][2][1], dp[i - 1][1][0] - prices[i])dp[i][1][0] = Math.max(dp[i - 1][1][0], dp[i - 1][1][1] + prices[i])dp[i][1][1] = Math.max(dp[i - 1][1][1], dp[i - 1][0][0] - prices[i])            = Math.max(dp[i - 1][1][1], -prices[i])// k=0時(shí) 沒有交易次數(shù)，dp[i - 1][0][0] = 0//去掉i這一維度dp[2][0] = Math.max(dp[2][0], dp[2][1] + prices[i])dp[2][1] = Math.max(dp[2][1], dp[1][0] - prices[i])dp[1][0] = Math.max(dp[1][0], dp[1][1] + prices[i])dp[1][1] = Math.max(dp[1][1], dp[0][0] - prices[i])            = Math.max(dp[1][1], -prices[i])// k=0時(shí) 沒有交易次數(shù)，dp[i - 1][0][0] = 0

完整代碼

//和前面一樣 我們直接降維const maxProfit = function (prices) {    let buy_1 = -prices[0], sell_1 = 0    let buy_2 = -prices[0], sell_2 = 0    let n = prices.length    for (let i = 1; i < n; i++) {        sell_2 = Math.max(sell_2, buy_2 + prices[i])        buy_2 = Math.max(buy_2, sell_1 - prices[i])        sell_1 = Math.max(sell_1, buy_1 + prices[i])        buy_1 = Math.max(buy_1, -prices[i])    }    return sell_2}

188. 買賣股票的最佳時(shí)機(jī) IV (hard) 限定交易次數(shù) 最多次數(shù)為 k

const maxProfit = function (k, prices) {    let n = prices.length;    let profit = new Array(k);//和123題一樣 求出所有k的狀態(tài)    // 初始化k次交易買入賣出的利潤(rùn)    for (let j = 0; j <= k; j++) {        profit[j] = {            buy: -prices[0],//表示有股票            sell: 0,//表示沒有股票        };    }    for (let i = 0; i < n; i++) {        for (let j = 1; j <= k; j++) {            //122題可以交易無(wú)數(shù)次，188交易k次，所以直接在加一層k循環(huán)就可以            //122最后的遞推方程：            //sell = Math.max(sell, buy + prices[i]);                //buy = Math.max(buy, -prices[i]);            profit[j] = {                sell: Math.max(profit[j].sell, profit[j].buy + prices[i]),                buy: Math.max(profit[j].buy, profit[j - 1].sell - prices[i]),            };        }    }    return profit[k].sell; //返回第k次清空手中的股票之后的最大利潤(rùn)};

309. 最佳買賣股票時(shí)機(jī)含冷凍期(medium) 含有交易冷凍期

狀態(tài)轉(zhuǎn)移方程

dp[i][k][0] = Math.max(dp[i - 1][k][0], dp[i - 1][k][1] + prices[i])//冷卻時(shí)間1天，所以要從 i - 2 天轉(zhuǎn)移狀態(tài)//買入，賣出 ---- 冷凍期 ----  買入，賣出dp[i][k][1] = Math.max(dp[i - 1][k][1], dp[i - 2][k - 1][0] - prices[i])

題目不限制k的大小，可以舍去

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 - 2][0] - prices[i])//降維idp[0] = Math.max(dp[0], dp[1] + prices[i])dp[1] = Math.max(dp[1], profit_freeze - prices[i])

完整代碼

const maxProfit = function (prices) {    let n = prices.length;    let buy = -prices[0];//手中有股票    let sell = 0;//沒有股票    let profit_freeze = 0;    for (let i = 1; i < n; i++) {        let temp = sell;        sell = Math.max(sell, buy + prices[i]);        buy = Math.max(buy, profit_freeze - prices[i]);        profit_freeze = temp;    }    return sell;};

714. 買賣股票的最佳時(shí)機(jī)含手續(xù)費(fèi) (medium) 每次交易含手續(xù)費(fèi)

狀態(tài)轉(zhuǎn)移方程

//每次交易要支付手續(xù)費(fèi) 我們定義在賣出的時(shí)候扣手續(xù)費(fèi)dp[i][0] = max(dp[i - 1][0], dp[i - 1][1] + prices[i] - fee)dp[i][1] = max(dp[i - 1][1], dp[i - 1][0] - prices[i])

完整代碼

const maxProfit = function (prices, fee) {    let sell = 0;//賣出    let buy = -prices[0];//買入    for (let i = 1; i < prices.length; i++) {        sell = Math.max(sell, buy + prices[i] - fee);        buy = Math.max(buy, sell - prices[i]);    }    return sell;};

322. 零錢兌換 (medium)

不能用貪心做，反例，coins=[1, 3, 5, 6, 7]，amount=30，用貪心先用最大的面額7，在用2個(gè)1，4 * 7 + 2 * 1 = 30，但是我們用5個(gè)6，5 * 6 = 30 就能用最少的硬幣兌換完成

方法1.動(dòng)態(tài)規(guī)劃

  • 思路：dp[i]表示兌換面額i所需要的最少硬幣，因?yàn)橛矌艧o(wú)限，所以可以自底向上計(jì)算dp[i]，對(duì)于dp[0~i]的每個(gè)狀態(tài)，循環(huán)coins數(shù)組，尋找可以兌換的組合，用i面額減去當(dāng)前硬幣價(jià)值，dp[i-coin]在加上一個(gè)硬幣數(shù)就是dp[i],最后取最小值就是答案，狀態(tài)轉(zhuǎn)移方程就是dp[i] = Math.min(dp[i], dp[i - coin] + 1);
  • 復(fù)雜度分析：時(shí)間復(fù)雜度是O(sn)，s是兌換金額，n是硬幣數(shù)組長(zhǎng)度，一共需要計(jì)算s個(gè)狀態(tài)，每個(gè)狀態(tài)需要遍歷n個(gè)面額來轉(zhuǎn)移狀態(tài)。空間復(fù)雜度是O(s)，也就是dp數(shù)組的長(zhǎng)度

Js:

var coinChange = function (coins, amount) {    let dp = new Array(amount + 1).fill(Infinity);//初始化dp數(shù)組    dp[0] = 0;//面額0只需要0個(gè)硬幣兌換    for (let i = 1; i <= amount; i++) {//循環(huán)面額        for (let coin of coins) {//循環(huán)硬幣數(shù)組            if (i - coin >= 0) {//當(dāng)面額大于硬幣價(jià)值時(shí)                //dp[i - coin]： 當(dāng)前面額i減當(dāng)前硬幣價(jià)值所需要的最少硬幣                //dp[i] 可由 dp[i - coin] + 1 轉(zhuǎn)換而來                dp[i] = Math.min(dp[i], dp[i - coin] + 1);            }        }    }    return dp[amount] === Infinity ? -1 : dp[amount];//如果dp[amount] === Infinity，則無(wú)法兌換};

Java:

public class Solution {    public int coinChange(int[] coins, int amount) {        int max = amount + 1;        int[] dp = new int[amount + 1];        Arrays.fill(dp, max);        dp[0] = 0;        for (int i = 1; i <= amount; i++) {            for (int j = 0; j < coins.length; j++) {                if (coins[j] <= i) {                    dp[i] = Math.min(dp[i], dp[i - coins[j]] + 1);                }            }        }        return dp[amount] > amount ? -1 : dp[amount];    }}

72. 編輯距離 （hard）

方法1.動(dòng)態(tài)規(guī)劃

  • 思路：dp[i][j] 表示word1前i個(gè)字符和word2前j個(gè)字符的最少編輯距離。
    1. 如果word1[i-1] === word2[j-1],說明最后一個(gè)字符不用操作，此時(shí)dp[i][j] = dp[i-1][j-1]，即此時(shí)的最小操作數(shù)和word1和word2都減少一個(gè)字符的最小編輯數(shù)相同
    2. 如果word1[i-1] !== word2[j-1]，則分為三種情況
      1. word1刪除最后一個(gè)字符，狀態(tài)轉(zhuǎn)移成dp[i-1][j]，即dp[i][j] = dp[i-1][j] + 1，+1指刪除操作
      2. word1在最后加上一個(gè)字符，狀態(tài)轉(zhuǎn)移成dp[i][j-1]，即dp[i][j] = dp[i][j-1] + 1，+1指增加操作
      3. word1替換最后一個(gè)字符，狀態(tài)轉(zhuǎn)移成dp[i-1][j-1]，即dp[i] [j] = dp[i-1] [j-1] + 1，+1指替換操作
  • 復(fù)雜度：時(shí)間復(fù)雜度是O(mn) ，m是word1的長(zhǎng)度，n是word2的長(zhǎng)度。空間復(fù)雜度是O(mn) ，需要用m * n大小的二維數(shù)字存儲(chǔ)狀態(tài)。

Js:

const minDistance = (word1, word2) => {    let dp = Array.from(Array(word1.length + 1), () => Array(word2.length + 1).fill(0));    //初始化數(shù)組，word1前i個(gè)字符最少需要i次操作，比如i次刪除變成word2    for (let i = 1; i <= word1.length; i++) {        dp[i][0] = i;    }    //初始化數(shù)組，word2前i個(gè)字符最少需要i次操作，比如j次插入變成word1    for (let j = 1; j <= word2.length; j++) {        dp[0][j] = j;    }    for (let i = 1; i <= word1.length; i++) {        //循環(huán)word1和word2        for (let j = 1; j <= word2.length; j++) {            if (word1[i - 1] === word2[j - 1]) {                //如果word1[i-1] === word2[j-1],說明最后一個(gè)字符不用操作。                dp[i][j] = dp[i - 1][j - 1];            } else {                //dp[i-1][j] + 1：對(duì)應(yīng)刪除                //dp[i][j-1] + 1：對(duì)應(yīng)新增                // dp[i-1][j-1] + 1：對(duì)應(yīng)替換操作                dp[i][j] = Math.min(dp[i - 1][j] + 1, dp[i][j - 1] + 1, dp[i - 1][j - 1] + 1);            }        }    }    return dp[word1.length][word2.length];};

Java:

public int minDistance(String word1, String word2) {    int m = word1.length();    int n = word2.length();    int[][] dp = new int[m + 1][n + 1];    for (int i = 1; i <= m; i++) {        dp[i][0] =  i;    }    for (int j = 1; j <= n; j++) {        dp[0][j] = j;    }    for (int i = 1; i <= m; i++) {        for (int j = 1; j <= n; j++) {            if (word1.charAt(i - 1) == word2.charAt(j - 1)) {                dp[i][j] = dp[i - 1][j - 1];            } else {                dp[i][j] = Math.min(Math.min(dp[i - 1][j - 1], dp[i][j - 1]), dp[i - 1][j]) + 1;            }        }    }    return dp[m][n];}

10. 正則表達(dá)式匹配(hard)

方法1.動(dòng)態(tài)規(guī)劃

  • 思路：dp[i][j] 表示 s 的前 i 個(gè)字符能否和p的前j個(gè)字符匹配，分為四種情況，看圖
  • 復(fù)雜度：時(shí)間復(fù)雜度O(mn)，m,n分別是字符串s和p的長(zhǎng)度，需要嵌套循環(huán)s和p。空間復(fù)雜度O(mn)，dp數(shù)組所占的空間

js:

//dp[i][j]表示s的前i個(gè)字符能否和p的前j個(gè)字符匹配const isMatch = (s, p) => {    if (s == null || p == null) return false;//極端情況 s和p都是空 返回false    const sLen = s.length, pLen = p.length;    const dp = new Array(sLen + 1);//因?yàn)槲恢檬菑?開始的，第0個(gè)位置是空字符串 所以初始化長(zhǎng)度是sLen + 1    for (let i = 0; i < dp.length; i++) {//初始化dp數(shù)組        dp[i] = new Array(pLen + 1).fill(false); // 將項(xiàng)默認(rèn)為false    }    // base case s和p第0個(gè)位置是匹配的    dp[0][0] = true;    for (let j = 1; j < pLen + 1; j++) {//初始化dp的第一列，此時(shí)s的位置是0        //情況1:如果p的第j-1個(gè)位置是*，則j的狀態(tài)等于j-2的狀態(tài)        //例如：s= p=a* 相當(dāng)于p向前看2個(gè)位置如果匹配，則*相當(dāng)于重復(fù)0個(gè)字符        if (p[j - 1] == "*") dp[0][j] = dp[0][j - 2];    }    // 迭代    for (let i = 1; i < sLen + 1; i++) {        for (let j = 1; j < pLen + 1; j++) {            //情況2:如果s和p當(dāng)前字符是相等的 或者p當(dāng)前位置是. 則當(dāng)前的dp[i][j] 可由dp[i - 1][j - 1]轉(zhuǎn)移過來            //當(dāng)前位置相匹配，則s和p都向前看一位 如果前面所有字符相匹配 則當(dāng)前位置前面的所有字符也匹配            //例如：s=XXXa p=XXX. 或者 s=XXXa p=XXXa            if (s[i - 1] == p[j - 1] || p[j - 1] == ".") {                dp[i][j] = dp[i - 1][j - 1];            } else if (p[j - 1] == "*") {//情況3:進(jìn)入當(dāng)前字符不匹配的分支 如果當(dāng)前p是* 則有可能會(huì)匹配                //s當(dāng)前位置和p前一個(gè)位置相同 或者p前一個(gè)位置等于. 則有三種可能                //其中一種情況能匹配 則當(dāng)前位置的狀態(tài)也能匹配                //dp[i][j - 2]：p向前看2個(gè)位置，相當(dāng)于*重復(fù)了0次，                //dp[i][j - 1]：p向前看1個(gè)位置，相當(dāng)于*重復(fù)了1次                //dp[i - 1][j]：s向前看一個(gè)位置，相當(dāng)于*重復(fù)了n次                //例如 s=XXXa p=XXXa*                if (s[i - 1] == p[j - 2] || p[j - 2] == ".") {                    dp[i][j] = dp[i][j - 2] || dp[i][j - 1] || dp[i - 1][j];                } else {                    //情況4:s當(dāng)前位置和p前2個(gè)位置不匹配，則相當(dāng)于*重復(fù)了0次                    //例如 s=XXXb p=XXXa* 當(dāng)前位置的狀態(tài)和p向前看2個(gè)位置的狀態(tài)相同                    dp[i][j] = dp[i][j - 2];                }            }        }    }    return dp[sLen][pLen]; // 長(zhǎng)為sLen的s串 是否匹配 長(zhǎng)為pLen的p串};

Java:

class Solution {    public boolean isMatch(String s, String p) {        if (p==null){            if (s==null){                return true;            }else{                return false;            }        }        if (s==null && p.length()==1){            return false;        }        int m = s.length()+1;        int n = p.length()+1;        boolean[][]dp = new boolean[m][n];        dp[0][0] = true;        for (int j=2;j

312. 戳氣球 (hard)

方法1:動(dòng)態(tài)規(guī)劃

  • 思路：dp[i][j] 表示開區(qū)間 (i,j) 能拿到的的金幣，k是這個(gè)區(qū)間 最后一個(gè) 被戳爆的氣球，枚舉i和j，遍歷所有區(qū)間，i-j能獲得的最大數(shù)量的金幣等于 戳破當(dāng)前的氣球獲得的金錢加上之前i-k、k-j區(qū)間中已經(jīng)獲得的金幣
  • 復(fù)雜度：時(shí)間復(fù)雜度O(n^3)，n是氣球的數(shù)量，三層遍歷。空間復(fù)雜度O(n^2)，dp數(shù)組的空間。

js：

var maxCoins = function (nums) {    const n = nums.length;    let points = [1, ...nums, 1]; //兩邊添加虛擬氣球    const dp = Array.from(Array(n + 2), () => Array(n + 2).fill(0)); //dp數(shù)組初始化    //自底向上轉(zhuǎn)移狀態(tài)    for (let i = n; i >= 0; i--) {        //i不斷減小        for (let j = i + 1; j < n + 2; j++) {            //j不斷擴(kuò)大            for (let k = i + 1; k < j; k++) {                //枚舉k在i和j中的所有可能                //i-j能獲得的最大數(shù)量的金幣等于 戳破當(dāng)前的氣球獲得的金錢加上之前i-k,k-j區(qū)間中已經(jīng)獲得的金幣                dp[i][j] = Math.max(                    //挑戰(zhàn)最大值                    dp[i][j],                    dp[i][k] + dp[k][j] + points[j] * points[k] * points[i]                );            }        }    }    return dp[0][n + 1];};

java：

class Solution {    public int maxCoins(int[] nums) {        int n = nums.length;        int[][] dp = new int[n + 2][n + 2];        int[] val = new int[n + 2];        val[0] = val[n + 1] = 1;        for (int i = 1; i <= n; i++) {            val[i] = nums[i - 1];        }        for (int i = n - 1; i >= 0; i--) {            for (int j = i + 2; j <= n + 1; j++) {                for (int k = i + 1; k < j; k++) {                    int sum = val[i] * val[k] * val[j];                    sum += dp[i][k] + dp[k][j];                    dp[i][j] = Math.max(dp[i][j], sum);                }            }        }        return dp[0][n + 1];    }}

343. 整數(shù)拆分 (medium)

  • 思路：dp[i]為正整數(shù)i拆分之后的最大乘積，循環(huán)數(shù)字n，對(duì)每個(gè)數(shù)字進(jìn)行拆分，取最大的乘積，狀態(tài)轉(zhuǎn)移方程：dp[i] = Math.max(dp[i], dp[i - j] * j, (i - j) * j)，j*(i-j)表示把i拆分為j和i-j兩個(gè)數(shù)相乘，j * dp[i-j]表示把i拆分成j和繼續(xù)把(i-j)這個(gè)數(shù)拆分，取(i-j)拆分結(jié)果中的最大乘積與j相乘
  • 復(fù)雜度：時(shí)間復(fù)雜度O(n^2)，兩層循環(huán)。空間復(fù)雜度O(n)，dp數(shù)組的空間

js：

var integerBreak = function (n) {    //dp[i]為正整數(shù)i拆分之后的最大乘積    let dp = new Array(n + 1).fill(0);    dp[2] = 1;    for (let i = 3; i <= n; i++) {        for (let j = 1; j < i; j++) {            //j*(i-j)表示把i拆分為j和i-j兩個(gè)數(shù)相乘            //j*dp[i-j]表示把i拆分成j和繼續(xù)把(i-j)這個(gè)數(shù)拆分，取(i-j)拆分結(jié)果中的最大乘積與j相乘            dp[i] = Math.max(dp[i], dp[i - j] * j, (i - j) * j);        }    }    return dp[n];};

java：

class Solution {    public int integerBreak(int n) {        int[] dp = new int[n+1];         dp[2] = 1;//初始狀態(tài)        for (int i = 3; i <= n; ++i) {            for (int j = 1; j < i - 1; ++j) {                dp[i] = Math.max(dp[i], Math.max(j * (i - j), j * dp[i - j]));            }        }        return dp[n];    }}

0-1背包問題

0-1背包問題指的是有n個(gè)物品和容量為j的背包，weight數(shù)組中記錄了n個(gè)物品的重量，位置i的物品重量是weight[i]，value數(shù)組中記錄了n個(gè)物品的價(jià)值，位置i的物品價(jià)值是vales[i]，每個(gè)物品只能放一次到背包中，問將那些物品裝入背包，使背包的價(jià)值最大。

舉例：

我們用動(dòng)態(tài)規(guī)劃的方式來做

  • 狀態(tài)定義：dp[i][j] 表示從前i個(gè)物品里任意取，放進(jìn)容量為j的背包，價(jià)值總和最大是多少

  • 狀態(tài)轉(zhuǎn)移方程： dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - weight[i]] + value[i]); 每個(gè)物品有放入背包和不放入背包兩種情況

    1. 當(dāng)j - weight[i]<0：表示裝不下i號(hào)元素了，不放入背包，此時(shí)dp[i][j] = dp[i - 1][j]，dp[i] [j]取決于前i-1中的物品裝入容量為j的背包中的最大價(jià)值
    2. 當(dāng)j - weight[i]>=0：可以選擇放入或者不放入背包。
      放入背包則：dp[i][j] = dp[i - 1][j - weight[i]] + value[i]， dp[i - 1][j - weight[i]] 表示i-1中的物品裝入容量為j-weight[i]的背包中的最大價(jià)值，然后在加上放入的物品的價(jià)值value[i]就可以將狀態(tài)轉(zhuǎn)移到dp[i][j]。
      不放入背包則：dp[i][j] = dp[i - 1] [j]，在這兩種情況中取較大者。

  • 初始化dp數(shù)組：dp[i][0]表示背包的容積為0，則背包的價(jià)值一定是0，dp[0][j]表示第0號(hào)物品放入背包之后背包的價(jià)值

  • 最終需要返回值：就是dp數(shù)組的最后一行的最后一列

循環(huán)完成之后的dp數(shù)組如下圖

js：

function testWeightBagProblem(wight, value, size) {    const len = wight.length,        dp = Array.from({ length: len + 1 }).map(//初始化dp數(shù)組            () => Array(size + 1).fill(0)        );    //注意我們讓i從1開始，因?yàn)槲覀冇袝r(shí)會(huì)用到i - 1，為了防止數(shù)組越界    //所以dp數(shù)組在初始化的時(shí)候，長(zhǎng)度是wight.length+1    for (let i = 1; i <= len; i++) {        for (let j = 0; j <= size; j++) {            //因?yàn)閣eight的長(zhǎng)度是wight.length+1，并且物品下標(biāo)從1開始，所以這里i要減1            if (wight[i - 1] <= j) {                dp[i][j] = Math.max(                    dp[i - 1][j],                    value[i - 1] + dp[i - 1][j - wight[i - 1]]                )            } else {                dp[i][j] = dp[i - 1][j];            }        }    }    return dp[len][size];}function test() {    console.log(testWeightBagProblem([1, 3, 4], [15, 20, 30], 4));}test();

狀態(tài)壓縮

根據(jù)狀態(tài)轉(zhuǎn)移方程dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - weight[i]] + value[i])，第i行只與第i-1行狀態(tài)相關(guān)，所以我們可以用滾動(dòng)數(shù)組進(jìn)行狀態(tài)壓縮，其次我們注意到，j只與j前面的狀態(tài)相關(guān)，所以只用一個(gè)數(shù)組從后向前計(jì)算狀態(tài)就可以了。

動(dòng)畫過大，點(diǎn)擊查看

function testWeightBagProblem2(wight, value, size) {    const len = wight.length,        dp = Array(size + 1).fill(0);    for (let i = 1; i <= len; i++) {        //從后向前計(jì)算，如果從前向后的話，最新的值會(huì)覆蓋老的值，導(dǎo)致計(jì)算結(jié)果不正確        //dp[i][j] = Math.max(dp[i - 1][j], dp[i - 1][j - wight[i - 1]] + value[i - 1])        for (let j = size; j >= wight[i - 1]; j--) {            dp[j] = Math.max(dp[j], dp[j - wight[i - 1]] + value[i - 1] );        }    }    return dp[size];}

416. 分割等和子集 （medium）

  • 思路：本題可以看成是0-1背包問題，給一個(gè)可裝載重量為 sum / 2 的背包和 N 個(gè)物品，每個(gè)物品的重量記錄在 nums 數(shù)組中，問是否在一種裝法，能夠恰好將背包裝滿？dp[i][j]表示前i個(gè)物品是否能裝滿容積為j的背包，當(dāng)dp[i][j]為true時(shí)表示恰好可以裝滿。每個(gè)數(shù)都有放入背包和不放入兩種情況，分析方法和0-1背包問題一樣。
  • 復(fù)雜度：時(shí)間復(fù)雜度O(n*sum)，n是nums數(shù)組長(zhǎng)度，sum是nums數(shù)組元素的和。空間復(fù)雜度O(n * sum)，狀態(tài)壓縮之后是O(sum)

js：

//可以看成是0-1背包問題，給一個(gè)可裝載重量為 sum / 2 的背包和 N 個(gè)物品，//每個(gè)物品的重量記錄在 nums 數(shù)組中，問是否在一種裝法，能夠恰好將背包裝滿？var canPartition = function (nums) {    let sum = 0    let n = nums.length    for (let i = 0; i < n; i++) {        sum += nums[i]    }    if (sum % 2 !== 0) {//如果是奇數(shù)，那么分割不了，直接返回false        return false    }    sum = sum / 2    //dp[i][j]表示前i個(gè)物品是否能裝滿容積為j的背包，當(dāng)dp[i][j]為true時(shí)表示恰好可以裝滿    //最后求的是 dp[n][sum] 表示前n個(gè)物品能否把容量為sum的背包恰好裝滿    //dp數(shù)組長(zhǎng)度是n+1，而且是二維數(shù)組，第一維表示物品的索引，第二個(gè)維度表示背包大小    let dp = new Array(n + 1).fill(0).map(() => new Array(sum + 1).fill(false))    //dp數(shù)組初始化，dp[..][0] = true表示背包容量為0，這時(shí)候就已經(jīng)裝滿了，    //dp[0][..] = false 表示沒有物品，肯定裝不滿    for (let i = 0; i <= n; i++) {        dp[i][0] = true    }    for (let i = 1; i <= n; i++) {//i從1開始遍歷防止取dp[i - 1][j]的時(shí)候數(shù)組越界        let num = nums[i - 1]        //j從1開始，j為0的情況已經(jīng)在dp數(shù)組初始化的時(shí)候完成了        for (let j = 1; j <= sum; j++) {            if (j - num < 0) {//背包容量不足 不能放入背包                dp[i][j] = dp[i - 1][j];//dp[i][j]取決于前i-1個(gè)物品是否能前好裝滿j的容量            } else {                //dp[i - 1][j]表示不裝入第i個(gè)物品                //dp[i - 1][j-num]表示裝入第i個(gè)，此時(shí)需要向前看前i - 1是否能裝滿j-num                //和背包的區(qū)別，這里只是返回true和false 表示能否裝滿，不用計(jì)算價(jià)值                dp[i][j] = dp[i - 1][j] || dp[i - 1][j - num];            }        }    }    return dp[n][sum]};//狀態(tài)轉(zhuǎn)移方程 F[i, target] = F[i - 1, target] || F[i - 1, target - nums[i]]//第 n 行的狀態(tài)只依賴于第 n-1 行的狀態(tài)//狀態(tài)壓縮var canPartition = function (nums) {    let sum = nums.reduce((acc, num) => acc + num, 0);    if (sum % 2) {        return false;    }    sum = sum / 2;    const dp = Array.from({ length: sum + 1 }).fill(false);    dp[0] = true;    for (let i = 1; i <= nums.length; i++) {        //從后向前計(jì)算，如果從前向后的話，最新的值會(huì)覆蓋老的值，導(dǎo)致計(jì)算結(jié)果不正確        for (let j = sum; j > 0; j--) {            dp[j] = dp[j] || (j - nums[i] >= 0 && dp[j - nums[i]]);        }    }    return dp[sum];};

java：

public class Solution {    public boolean canPartition(int[] nums) {        int len = nums.length;        int sum = 0;        for (int num : nums) {            sum += num;        }        if ((sum & 1) == 1) {            return false;        }        int target = sum / 2;        boolean[][] dp = new boolean[len][target + 1];        dp[0][0] = true;        if (nums[0] <= target) {            dp[0][nums[0]] = true;        }        for (int i = 1; i < len; i++) {            for (int j = 0; j <= target; j++) {                dp[i][j] = dp[i - 1][j];                if (nums[i] <= j) {                    dp[i][j] = dp[i - 1][j] || dp[i - 1][j - nums[i]];                }            }            if (dp[i][target]) {                return true;            }        }        return dp[len - 1][target];    }}//狀態(tài)壓縮public class Solution {    public boolean canPartition(int[] nums) {        int len = nums.length;        int sum = 0;        for (int num : nums) {            sum += num;        }        if ((sum & 1) == 1) {            return false;        }        int target = sum / 2;        boolean[] dp = new boolean[target + 1];        dp[0] = true;        if (nums[0] <= target) {            dp[nums[0]] = true;        }        for (int i = 1; i < len; i++) {            for (int j = target; nums[i] <= j; j--) {                if (dp[target]) {                    return true;                }                dp[j] = dp[j] || dp[j - nums[i]];            }        }        return dp[target];    }}

198. 打家劫舍 （medium）

  • 思路：dp[i]表示0-i能偷的最大金額，dp[i]由兩種情況中的最大值轉(zhuǎn)移過來
    1. dp[i - 2] + nums[i] 表示偷當(dāng)前位置，那么i-1的位置不能偷，而且需要加上dp[i-2],也就是前i-2個(gè)房間的金錢
    2. dp[i - 1]表示偷當(dāng)前位置，只偷i-1的房間
  • 復(fù)雜度：時(shí)間復(fù)雜度O(n)，遍歷一次數(shù)組，空間復(fù)雜度O(1)，狀態(tài)壓縮之后是O(1)，沒有狀態(tài)壓縮是O(n)

js：

//dp[i]表示0-i能偷的最大金額const rob = (nums) => {    const len = nums.length;    const dp = [nums[0], Math.max(nums[0], nums[1])]; //初始化dp數(shù)組的前兩項(xiàng)    for (let i = 2; i < len; i++) {        //從第三個(gè)位置開始遍歷        //dp[i - 2] + nums[i] 表示偷當(dāng)前位置，那么i-1的位置不能偷，        //而且需要加上dp[i-2],也就是前i-2個(gè)房間的金錢        //dp[i - 1]表示偷當(dāng)前位置，只偷i-1的房間        dp[i] = Math.max(dp[i - 2] + nums[i], dp[i - 1]);    }    return dp[len - 1]; //返回最后最大的項(xiàng)};//狀態(tài)壓縮var rob = function (nums) {    if(nums.length === 1) return nums[0]    let len = nums.length;    let dp_0 = nums[0],        dp_1 = Math.max(nums[0], nums[1]);    let dp_max = dp_1;    for (let i = 2; i < len; i++) {        dp_max = Math.max(            dp_1, //不搶當(dāng)前家            dp_0 + nums[i] //搶當(dāng)前家        );        dp_0 = dp_1; //滾動(dòng)交換變量        dp_1 = dp_max;    }    return dp_max;};

java:

class Solution {    public int rob(int[] nums) {        if (nums == null || nums.length == 0) {            return 0;        }        int length = nums.length;        if (length == 1) {            return nums[0];        }        int[] dp = new int[length];        dp[0] = nums[0];        dp[1] = Math.max(nums[0], nums[1]);        for (int i = 2; i < length; i++) {            dp[i] = Math.max(dp[i - 2] + nums[i], dp[i - 1]);        }        return dp[length - 1];    }}//狀態(tài)壓縮class Solution {    public int rob(int[] nums) {        if (nums == null || nums.length == 0) {            return 0;        }        int len = nums.length;        int dp_0 = 0,            dp_1 = nums[0];        int dp_max = nums[0];        for (int i = 2; i <= len; i++) {            dp_max = Math.max(                dp_1, //不搶當(dāng)前家                dp_0 + nums[i - 1] //搶當(dāng)前家            );            dp_0 = dp_1; //滾動(dòng)交換變量            dp_1 = dp_max;        }        return dp_max;    }}

64. 最小路徑和 (medium)

  • 思路：dp[i][j]表示從矩陣左上角到（i，j）這個(gè)網(wǎng)格對(duì)應(yīng)的最小路徑和，只要從上到下，從左到右遍歷網(wǎng)格，當(dāng)前最小路徑和就是當(dāng)前的數(shù)值加上上面和左邊左小的。
  • 復(fù)雜度：時(shí)間復(fù)雜度O(mn)，m、n分別是矩陣的長(zhǎng)和寬。空間復(fù)雜度如果原地修改是O(1)，如果新建dp數(shù)組就是O(mn)

js：

var minPathSum = function(dp) {    let row = dp.length, col = dp[0].length    for(let i = 1; i < row; i++)//初始化第一列        dp[i][0] += dp[i - 1][0]    for(let j = 1; j < col; j++)//初始化第一行        dp[0][j] += dp[0][j - 1]    for(let i = 1; i < row; i++)        for(let j = 1; j < col; j++)            dp[i][j] += Math.min(dp[i - 1][j], dp[i][j - 1])//取上面和左邊最小的    return dp[row - 1][col - 1]};

java：

class Solution {    public int minPathSum(int[][] grid) {        if (grid == null || grid.length == 0 || grid[0].length == 0) {            return 0;        }        int rows = grid.length, columns = grid[0].length;        int[][] dp = new int[rows][columns];        dp[0][0] = grid[0][0];        for (int i = 1; i < rows; i++) {            dp[i][0] = dp[i - 1][0] + grid[i][0];        }        for (int j = 1; j < columns; j++) {            dp[0][j] = dp[0][j - 1] + grid[0][j];        }        for (int i = 1; i < rows; i++) {            for (int j = 1; j < co

文章版權(quán)歸作者所有，未經(jīng)允許請(qǐng)勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。

轉(zhuǎn)載請(qǐng)注明本文地址：http://m.specialneedsforspecialkids.com/yun/124236.html