大廠算法面試之leetcode精講3.動態規劃

視頻教程（高效學習）:點擊學習

目錄：

1.開篇介紹

2.時間空間復雜度

3.動態規劃

4.貪心

5.二分查找

6.深度優先&廣度優先

7.雙指針

8.滑動窗口

9.位運算

10.遞歸&分治

11剪枝&回溯

12.堆

13.單調棧

14.排序算法

15.鏈表

16.set&map

17.棧

18.隊列

19.數組

20.字符串

21.樹

22.字典樹

23.并查集

24.其他類型題

什么是動態規劃

動態規劃，英文：Dynamic Programming，簡稱DP，將問題分解為互相重疊的子問題，通過反復求解子問題來解決原問題就是動態規劃，如果某一問題有很多重疊子問題，使用動態規劃來解是比較有效的。

求解動態規劃的核心問題是窮舉，但是這類問題窮舉有點特別，因為這類問題存在「重疊子問題」，如果暴力窮舉的話效率會極其低下。動態規劃問題一定會具備「最優子結構」，才能通過子問題的最值得到原問題的最值。另外，雖然動態規劃的核心思想就是窮舉求最值，但是問題可以千變萬化，窮舉所有可行解其實并不是一件容易的事，只有列出正確的「狀態轉移方程」才能正確地窮舉。重疊子問題、最優子結構、狀態轉移方程就是動態規劃三要素

動態規劃和其他算法的區別

  1. 動態規劃和分治的區別：動態規劃和分治都有最優子結構 ，但是分治的子問題不重疊
  2. 動態規劃和貪心的區別：動態規劃中每一個狀態一定是由上一個狀態推導出來的，這一點就區分于貪心，貪心沒有狀態推導，而是從局部直接選最優解，所以它永遠是局部最優，但是全局的解不一定是最優的。
  3. 動態規劃和遞歸的區別：遞歸和回溯可能存在非常多的重復計算，動態規劃可以用遞歸加記憶化的方式減少不必要的重復計算

動態規劃的解題方法

  • 遞歸+記憶化(自頂向下)
  • 動態規劃（自底向上）

解動態規劃題目的步驟

  1. 根據重疊子問題定義狀態
  2. 尋找最優子結構推導狀態轉移方程
  3. 確定dp初始狀態
  4. 確定輸出值

斐波那契的動態規劃的解題思路

動畫過大，點擊查看

暴力遞歸
//暴力遞歸復雜度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 = {}; // 對已算出的結果進行緩存    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);};
動態規劃
const fib = (n) => {    if (n <= 1) return n;    const dp = [0, 1];    for (let i = 2; i <= n; i++) {        //自底向上計算每個狀態        dp[i] = dp[i - 1] + dp[i - 2];    }    return dp[n];};
滾動數組優化
const fib = (n) => {    if (n <= 1) return n;    //滾動數組 dp[i]只和dp[i-1]、dp[i-2]相關，只維護長度為2的滾動數組，不斷替換數組元素    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;};
動態規劃 + 降維，（降維能減少空間復雜度，但不利于程序的擴展）
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;};

509. 斐波那契數（easy）

方法1.動態規劃
  • 思路：自底而上的動態規劃
  • 復雜度分析：時間復雜度O(n)，空間復雜度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.動態規劃

動畫過大，點擊查看

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

js:

var uniquePaths = function (m, n) {    const f = new Array(m).fill(0).map(() => new Array(n).fill(0)); //初始dp數組    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];};//狀態壓縮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];    }}//狀態壓縮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.動態規劃
  • 思路：和62題一樣，區別就是遇到障礙直接返回0
  • 復雜度：時間復雜度O(mn)，空間復雜度O(mn)，狀態壓縮之后是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數組    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];};//狀態壓縮var uniquePathsWithObstacles = function (obstacleGrid) {    let m = obstacleGrid.length;    let n = obstacleGrid[0].length;    let dp = Array(n).fill(0); //用0填充，因為現在有障礙物，當前dp數組元素的值還和obstacleGrid[i][j]有關    dp[0] = 1; //第一列 暫時用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) {                //只有當j>0 不是第一列了才能取到j - 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.動態規劃

  • 思路：因為每次可以爬 1 或 2 個臺階，所以到第n階臺階可以從第n-2或n-1上來，其實就是斐波那契的dp方程
  • 復雜度分析：時間復雜度O(n)，空間復雜度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階臺階可以從第n-2或n-1上來    }    return memo[n];};//狀態壓縮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;   // 當前的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. 完全平方數 (medium)

方法1:動態規劃

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

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

js：

var numSquares = function (n) {    const dp = [...Array(n)].map((_) => 0); //初始化dp數組 當n為0的時候    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++) {//枚舉前一個狀態            dp[i] = Math.min(dp[i], dp[i - j * j] + 1); // 動態轉移方程        }    }    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.動態規劃

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

Js:

const minimumTotal = (triangle) => {    const h = triangle.length;    // 初始化dp數組    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 { // 狀態轉移方程，上一層由它下面一層計算出                dp[i][j] = Math.min(dp[i + 1][j], dp[i + 1][j + 1]) + triangle[i][j];            }        }    }    return dp[0][0];};//狀態壓縮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];    }    // 從倒數第二列開始迭代    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. 乘積最大子數組 （medium）

方法1.動態規劃

  • 思路：

    1. 狀態定義：dp[i][0]表示從第 0 項到第 i 項范圍內的子數組的最小乘積，dp[i][1]表示從第 0 項到第 i 項范圍內的子數組的最大乘積

    2. 初始狀態：dp[0][0]=nums[0], dp[0][1]=nums[0]

    3. 分情況討論:

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

    4. 狀態轉移方程：

      • 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. 狀態壓縮：dp[i][x]只與dp[i][x]-1，所以只需定義兩個變量，prevMin = nums[0]，prevMax = nums[0]

    6. 狀態壓縮之后的方程：

      • prevMin = Math.min(prevMin num[i], prevMax num[i], nums[i])
      • prevMax = Math.max(prevMin num[i], prevMax num[i], nums[i])
  • 復雜度：時間復雜度O(n)，空間復雜度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. 買賣股票的最佳時機（easy）限定交易次數 k=1

122. 買賣股票的最佳時機 II（medium）交易次數無限制 k = +infinity

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

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

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

714. 買賣股票的最佳時機含手續費 (medium) 每次交易含手續費

第5，6道題相當于在第2道題的基礎上加了冷凍期和手續費的條件。

限制條件
  • 先買入才能賣出
  • 不能同時參加多筆交易，再次買入時，需要先賣出
  • k >= 0才能進行交易，否則沒有交易次數
定義操作
  • 買入
  • 賣出
  • 不操作
定義狀態
  • i: 天數
  • k: 交易次數，每次交易包含買入和賣出，這里我們只在買入的時候需要將 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]，因為最后一天賣出肯定比持有收益更高

狀態轉移方程
// 今天沒有持有股票，分為兩種情況// 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])//最大利潤就是這倆種情況的最大值

121. 買賣股票的最佳時機（easy）限定交易次數 k=1

狀態轉移方程

//第i天不持有 由 第i-1天不持有然后不操作 和 第i-1天持有然后賣出 兩種情況的最大值轉移過來dp[i][1][0] = Math.max(dp[i - 1][1][0], dp[i - 1][1][1] + prices[i])//第i天持有 由 第i-1天持有然后不操作 和 第i-1天不持有然后買入 兩種情況的最大值轉移過來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時 沒有交易次數，dp[i - 1][0][0] = 0

k是固定值1，不影響結果，所以可以不用管，簡化之后如下

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

完整代碼

//時間復雜度O(n) 空間復雜度O(n)，dp數組第二維是常數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];};

狀態壓縮，dp[i] 只和 dp[i - 1] 有關，去掉一維

//時間復雜度O(n) 空間復雜度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];};//語意化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. 買賣股票的最佳時機 II（medium）交易次數無限制 k = +infinity

狀態轉移方程

//第i天不持有 由 第i-1天不持有然后不操作 和 第i-1天持有然后賣出 兩種情況的最大值轉移過來dp[i][k][0] = Math.max(dp[i - 1][k][0], dp[i - 1][k][1] + prices[i])//第i天持有 由 第i-1天持有然后不操作 和 第i-1天不持有然后買入 兩種情況的最大值轉移過來dp[i][k][1] = Math.max(dp[i - 1][k][1], dp[i - 1][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 - 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];};

狀態壓縮，同樣dp[i] 只和 dp[i - 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], dp[0] - prices[i]);    }    return dp[0];};//語意化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. 買賣股票的最佳時機 III (hrad) 限定交易次數 k=2

狀態轉移方程

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對結果有影響 不能舍去，只能對k進行循環

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，直接寫出循環的結果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時 沒有交易次數，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時 沒有交易次數，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. 買賣股票的最佳時機 IV (hard) 限定交易次數 最多次數為 k

const maxProfit = function (k, prices) {    let n = prices.length;    let profit = new Array(k);//和123題一樣 求出所有k的狀態    // 初始化k次交易買入賣出的利潤    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題可以交易無數次，188交易k次，所以直接在加一層k循環就可以            //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次清空手中的股票之后的最大利潤};

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

狀態轉移方程

dp[i][k][0] = Math.max(dp[i - 1][k][0], dp[i - 1][k][1] + prices[i])//冷卻時間1天，所以要從 i - 2 天轉移狀態//買入，賣出 ---- 冷凍期 ----  買入，賣出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. 買賣股票的最佳時機含手續費 (medium) 每次交易含手續費

狀態轉移方程

//每次交易要支付手續費 我們定義在賣出的時候扣手續費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個1，4 * 7 + 2 * 1 = 30，但是我們用5個6，5 * 6 = 30 就能用最少的硬幣兌換完成

方法1.動態規劃

  • 思路：dp[i]表示兌換面額i所需要的最少硬幣，因為硬幣無限，所以可以自底向上計算dp[i]，對于dp[0~i]的每個狀態，循環coins數組，尋找可以兌換的組合，用i面額減去當前硬幣價值，dp[i-coin]在加上一個硬幣數就是dp[i],最后取最小值就是答案，狀態轉移方程就是dp[i] = Math.min(dp[i], dp[i - coin] + 1);
  • 復雜度分析：時間復雜度是O(sn)，s是兌換金額，n是硬幣數組長度，一共需要計算s個狀態，每個狀態需要遍歷n個面額來轉移狀態。空間復雜度是O(s)，也就是dp數組的長度

Js:

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

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.動態規劃

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

Js:

const minDistance = (word1, word2) => {    let dp = Array.from(Array(word1.length + 1), () => Array(word2.length + 1).fill(0));    //初始化數組，word1前i個字符最少需要i次操作，比如i次刪除變成word2    for (let i = 1; i <= word1.length; i++) {        dp[i][0] = i;    }    //初始化數組，word2前i個字符最少需要i次操作，比如j次插入變成word1    for (let j = 1; j <= word2.length; j++) {        dp[0][j] = j;    }    for (let i = 1; i <= word1.length; i++) {        //循環word1和word2        for (let j = 1; j <= word2.length; j++) {            if (word1[i - 1] === word2[j - 1]) {                //如果word1[i-1] === word2[j-1],說明最后一個字符不用操作。                dp[i][j] = dp[i - 1][j - 1];            } else {                //dp[i-1][j] + 1：對應刪除                //dp[i][j-1] + 1：對應新增                // dp[i-1][j-1] + 1：對應替換操作                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. 正則表達式匹配(hard)

方法1.動態規劃

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

js:

//dp[i][j]表示s的前i個字符能否和p的前j個字符匹配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);//因為位置是從0開始的，第0個位置是空字符串 所以初始化長度是sLen + 1    for (let i = 0; i < dp.length; i++) {//初始化dp數組        dp[i] = new Array(pLen + 1).fill(false); // 將項默認為false    }    // base case s和p第0個位置是匹配的    dp[0][0] = true;    for (let j = 1; j < pLen + 1; j++) {//初始化dp的第一列，此時s的位置是0        //情況1:如果p的第j-1個位置是*，則j的狀態等于j-2的狀態        //例如：s= p=a* 相當于p向前看2個位置如果匹配，則*相當于重復0個字符        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當前字符是相等的 或者p當前位置是. 則當前的dp[i][j] 可由dp[i - 1][j - 1]轉移過來            //當前位置相匹配，則s和p都向前看一位 如果前面所有字符相匹配 則當前位置前面的所有字符也匹配            //例如：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:進入當前字符不匹配的分支 如果當前p是* 則有可能會匹配                //s當前位置和p前一個位置相同 或者p前一個位置等于. 則有三種可能                //其中一種情況能匹配 則當前位置的狀態也能匹配                //dp[i][j - 2]：p向前看2個位置，相當于*重復了0次，                //dp[i][j - 1]：p向前看1個位置，相當于*重復了1次                //dp[i - 1][j]：s向前看一個位置，相當于*重復了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當前位置和p前2個位置不匹配，則相當于*重復了0次                    //例如 s=XXXb p=XXXa* 當前位置的狀態和p向前看2個位置的狀態相同                    dp[i][j] = dp[i][j - 2];                }            }        }    }    return dp[sLen][pLen]; // 長為sLen的s串 是否匹配 長為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:動態規劃

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

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數組初始化    //自底向上轉移狀態    for (let i = n; i >= 0; i--) {        //i不斷減小        for (let j = i + 1; j < n + 2; j++) {            //j不斷擴大            for (let k = i + 1; k < j; k++) {                //枚舉k在i和j中的所有可能                //i-j能獲得的最大數量的金幣等于 戳破當前的氣球獲得的金錢加上之前i-k,k-j區間中已經獲得的金幣                dp[i][j] = Math.max(                    //挑戰最大值                    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. 整數拆分 (medium)

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

js：

var integerBreak = function (n) {    //dp[i]為正整數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兩個數相乘            //j*dp[i-j]表示把i拆分成j和繼續把(i-j)這個數拆分，取(i-j)拆分結果中的最大乘積與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;//初始狀態        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個物品和容量為j的背包，weight數組中記錄了n個物品的重量，位置i的物品重量是weight[i]，value數組中記錄了n個物品的價值，位置i的物品價值是vales[i]，每個物品只能放一次到背包中，問將那些物品裝入背包，使背包的價值最大。

舉例：

我們用動態規劃的方式來做

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

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

    1. 當j - weight[i]<0：表示裝不下i號元素了，不放入背包，此時dp[i][j] = dp[i - 1][j]，dp[i] [j]取決于前i-1中的物品裝入容量為j的背包中的最大價值
    2. 當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]的背包中的最大價值，然后在加上放入的物品的價值value[i]就可以將狀態轉移到dp[i][j]。
      不放入背包則：dp[i][j] = dp[i - 1] [j]，在這兩種情況中取較大者。

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

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

循環完成之后的dp數組如下圖

js：

function testWeightBagProblem(wight, value, size) {    const len = wight.length,        dp = Array.from({ length: len + 1 }).map(//初始化dp數組            () => Array(size + 1).fill(0)        );    //注意我們讓i從1開始，因為我們有時會用到i - 1，為了防止數組越界    //所以dp數組在初始化的時候，長度是wight.length+1    for (let i = 1; i <= len; i++) {        for (let j = 0; j <= size; j++) {            //因為weight的長度是wight.length+1，并且物品下標從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();

狀態壓縮

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

動畫過大，點擊查看

function testWeightBagProblem2(wight, value, size) {    const len = wight.length,        dp = Array(size + 1).fill(0);    for (let i = 1; i <= len; i++) {        //從后向前計算，如果從前向后的話，最新的值會覆蓋老的值，導致計算結果不正確        //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背包問題，給一個可裝載重量為 sum / 2 的背包和 N 個物品，每個物品的重量記錄在 nums 數組中，問是否在一種裝法，能夠恰好將背包裝滿？dp[i][j]表示前i個物品是否能裝滿容積為j的背包，當dp[i][j]為true時表示恰好可以裝滿。每個數都有放入背包和不放入兩種情況，分析方法和0-1背包問題一樣。
  • 復雜度：時間復雜度O(n*sum)，n是nums數組長度，sum是nums數組元素的和。空間復雜度O(n * sum)，狀態壓縮之后是O(sum)

js：

//可以看成是0-1背包問題，給一個可裝載重量為 sum / 2 的背包和 N 個物品，//每個物品的重量記錄在 nums 數組中，問是否在一種裝法，能夠恰好將背包裝滿？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) {//如果是奇數，那么分割不了，直接返回false        return false    }    sum = sum / 2    //dp[i][j]表示前i個物品是否能裝滿容積為j的背包，當dp[i][j]為true時表示恰好可以裝滿    //最后求的是 dp[n][sum] 表示前n個物品能否把容量為sum的背包恰好裝滿    //dp數組長度是n+1，而且是二維數組，第一維表示物品的索引，第二個維度表示背包大小    let dp = new Array(n + 1).fill(0).map(() => new Array(sum + 1).fill(false))    //dp數組初始化，dp[..][0] = true表示背包容量為0，這時候就已經裝滿了，    //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]的時候數組越界        let num = nums[i - 1]        //j從1開始，j為0的情況已經在dp數組初始化的時候完成了        for (let j = 1; j <= sum; j++) {            if (j - num < 0) {//背包容量不足 不能放入背包                dp[i][j] = dp[i - 1][j];//dp[i][j]取決于前i-1個物品是否能前好裝滿j的容量            } else {                //dp[i - 1][j]表示不裝入第i個物品                //dp[i - 1][j-num]表示裝入第i個，此時需要向前看前i - 1是否能裝滿j-num                //和背包的區別，這里只是返回true和false 表示能否裝滿，不用計算價值                dp[i][j] = dp[i - 1][j] || dp[i - 1][j - num];            }        }    }    return dp[n][sum]};//狀態轉移方程 F[i, target] = F[i - 1, target] || F[i - 1, target - nums[i]]//第 n 行的狀態只依賴于第 n-1 行的狀態//狀態壓縮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++) {        //從后向前計算，如果從前向后的話，最新的值會覆蓋老的值，導致計算結果不正確        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];    }}//狀態壓縮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]由兩種情況中的最大值轉移過來
    1. dp[i - 2] + nums[i] 表示偷當前位置，那么i-1的位置不能偷，而且需要加上dp[i-2],也就是前i-2個房間的金錢
    2. dp[i - 1]表示偷當前位置，只偷i-1的房間
  • 復雜度：時間復雜度O(n)，遍歷一次數組，空間復雜度O(1)，狀態壓縮之后是O(1)，沒有狀態壓縮是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數組的前兩項    for (let i = 2; i < len; i++) {        //從第三個位置開始遍歷        //dp[i - 2] + nums[i] 表示偷當前位置，那么i-1的位置不能偷，        //而且需要加上dp[i-2],也就是前i-2個房間的金錢        //dp[i - 1]表示偷當前位置，只偷i-1的房間        dp[i] = Math.max(dp[i - 2] + nums[i], dp[i - 1]);    }    return dp[len - 1]; //返回最后最大的項};//狀態壓縮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, //不搶當前家            dp_0 + nums[i] //搶當前家        );        dp_0 = dp_1; //滾動交換變量        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];    }}//狀態壓縮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, //不搶當前家                dp_0 + nums[i - 1] //搶當前家            );            dp_0 = dp_1; //滾動交換變量            dp_1 = dp_max;        }        return dp_max;    }}

64. 最小路徑和 (medium)

  • 思路：dp[i][j]表示從矩陣左上角到（i，j）這個網格對應的最小路徑和，只要從上到下，從左到右遍歷網格，當前最小路徑和就是當前的數值加上上面和左邊左小的。
  • 復雜度：時間復雜度O(mn)，m、n分別是矩陣的長和寬。空間復雜度如果原地修改是O(1)，如果新建dp數組就是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

文章版權歸作者所有，未經允許請勿轉載,若此文章存在違規行為，您可以聯系管理員刪除。

轉載請注明本文地址：http://specialneedsforspecialkids.com/yun/124236.html