動態規劃 - Sayyiku

動態規劃的三大步驟#

動態規劃，無非就是利用歷史記錄，來避免我們的重複計算。而這些歷史記錄，我們得需要一些變量來保存，一般是用一維數組或者二維數組來保存。

** 步驟一：定義數組元素的含義。** 前面提到一般用數組來保存歷史記錄，假設用一維數組 dp []，這時候每個數組元素的含義非常重要。

** 步驟二：找出數組元素之間的關係式。** 動態規劃類似於我們高中學習時的歸納法，可以利用 dp [n-1]、dp [n-2]...dp [1]，進而推出 dp [n]，也就是可以利用歷史數據來推出新的元素值，所以我們要找出數組元素之間的關係式，例如 dp [n] = dp [n-1] + dp [n-2]，這個就是他們的關係式了。

** 步驟三：找出初始值。** 即便知道了數組元素之間的關係式，也需要根據初始值才能推導出 dp [n]。

青蛙跳台階#

一隻青蛙一次可以跳上 1 級台階，也可以跳上 2 級。求該青蛙跳上一個 n 級的台階總共有多少種跳法。

定義數組元素的含義：跳上一個 i 級的台階總共有 dp [i] 種跳法，我們的目標是求 dp [n]。
找出數組元素之間的關係式：對於這道題，由於情況可以選擇跳一級，也可以選擇跳兩級，所以青蛙到達第 i 級的台階有兩種方式：一種是從第 i-1 級跳上來，一種是從第 i-2 級跳上來，所以所有可能的跳法的 dp [i] = dp [i-1] + dp [i-2]。
找出初始值：dp [0] = 0; dp [1] = 1; dp [3] = 3;

得出求解代碼：

const f = (n) => {
  const dp = []
  dp[0] = 0
  dp[1] = 1
  dp[2] = 2
  for (let i = 3; i <= n; i++) {
    dp[i] = dp[i - 1] + dp[i - 2]
  }
  return dp[n]
}

console.log(f(2)) // 2
console.log(f(3)) // 3
console.log(f(4)) // 5
console.log(f(5)) // 8

不同路徑#

題目來源：不同路徑

一個機器人位於一個 m x n 網格的左上角。機器人每次只能向下或者向右移動一步。機器人試圖達到網格的右下角。問總共有多少條不同的路徑？

定義數組元素的含義：我們把網格看作一個二維數組，起點坐標為 (0,0)，右下角坐標為 (m-1)(n-1)，當機器人從左上角走到 (i,j) 這個位置時，一共有 dp[i][j] 種路徑，所以我們的目標是求 dp[m-1][n-1]。
找出數組元素之間的關係式：達到 (i,j) 這個位置有兩種方式：一種是從 (i-1,j) 這個位置到達，一種是從 (i,j-1) 這個位置到達，所以所有達到的方式 dp[i][j] = dp[i-1][j] + dp[i][j-1]。
找出初始值：可以易知，當 i=0 或者 j=0 時，只能往右或者往下，方式只有一種。

得出求解代碼：

var uniquePaths = function (m, n) {
  if (m <= 0 || n <= 0) {
    return 0
  }

  // 初始化二維數組
  const dp = new Array(m).fill(0).map((_) => new Array(n).fill(0))
  // 當只有一列時
  for (let i = 0; i < m; i++) {
    dp[i][0] = 1
  }
  // 當只有一行時
  for (let j = 0; j < n; j++) {
    dp[0][j] = 1
  }

  for (let i = 1; i < m; i++) {
    for (let j = 1; j < n; j++) {
      dp[i][j] = dp[i - 1][j] + dp[i][j - 1]
    }
  }

  return dp[m - 1][n - 1]
}

console.log(uniquePaths(3, 2)) // 3
console.log(uniquePaths(3, 3)) // 6
console.log(uniquePaths(2, 1)) // 1

最小路徑和#

題目來源：最小路徑和

給定一個包含非負整數的 m x n 網格，每次只能向下或者向右移動一步，請找出一條從左上角到右下角的路徑，使得路徑上的數字總和為最小。

定義數組元素的含義：我們把網格看作一個二維數組，起點坐標為 (0,0)，右下角坐標為 (m-1)(n-1)，當從左上角走到 (i,j) 這個位置時，最小路徑和為 dp[i][j]，所以我們的目標是求 dp[m-1][n-1]。
找出數組元素之間的關係式：達到 (i,j) 這個位置有兩種方式：一種是從 (i-1,j) 這個位置到達，一種是從 (i,j-1) 這個位置到達，所以最小路徑和 dp[i][j] = Math.min(dp[i - 1][j] + arr[i][j], dp[i][j - 1] + arr[i][j])。
找出初始值：可以易知，當 i=0 或者 j=0 時，只能往右或者往下，方式只有一種，最小路徑和也只有一種。

得出求解代碼：

var minPathSum = function (grid) {
  const m = grid.length,
    n = grid[0].length

  if (m <= 0 || n <= 0) {
    return 0
  }

  const dp = new Array(m).fill(0).map((_) => new Array(n).fill(0))

  dp[0][0] = grid[0][0]

  // 最左邊的列
  for (let i = 1; i < m; i++) {
    dp[i][0] = dp[i - 1][0] + grid[i][0]
  }
  // 最上面的行
  for (let j = 1; j < n; j++) {
    dp[0][j] = dp[0][j - 1] + grid[0][j]
  }

  for (let i = 1; i < m; i++) {
    for (let j = 1; j < n; j++) {
      dp[i][j] = Math.min(dp[i - 1][j] + grid[i][j], dp[i][j - 1] + grid[i][j])
    }
  }

  return dp[m - 1][n - 1]
}

const grid = [
  [1, 3, 1],
  [1, 5, 1],
  [4, 2, 1],
]

console.log(minPathSum(grid)) // 7  路徑 1→3→1→1→1 的總和最小

編輯距離#

題目來源：編輯距離

給你兩個單詞 word1 和 word2，請返回將 word1 轉換成 word2 所使用的最少操作數。你可以對一個單詞進行如下三種操作：

插入一個字符

刪除一個字符

替換一個字符

定義數組元素的含義：當字符串 word1 的長度為 i，字符串 word2 的長度為 j 時，將 word1 轉化為 word2 所使用的最少操作次數為 dp[i][j]。
找出數組元素之間的關係式：大部分情況下，dp[i][j] 和 dp[i-1][j]、dp[i][j-1]、dp[i-1][j-1] 肯定存在某種關係。這題中，我們找出其中關係如下：
如果 word1 [i] 與 word2 [j] 相等，這個時候不需要進行任何操作，顯然有 dp[i][j] = dp[i-1][j-1]。
如果 word1 [i] 與 word2 [j] 不相等，則有三種操作，我們需要找出這三種操作的最小值，則 dp[i][j] = min(dp[i-1][j-1],dp[i][j-1],dp[[i-1][j]]) + 1：
1. 如果把字符 word1 [i] 替換成與 word2 [j] 後相等，則有 dp[i][j] = dp[i-1][j-1] + 1
2. 如果在字符串 word1 末尾插入一個與 word2 [j] 相等的字符，則有 dp[i][j] = dp[i][j-1] + 1
3. 如果把字符 word1 [i] 刪除，則有 dp[i][j] = dp[i-1][j] + 1
找出初始值：當 dp[i][j] 中，如果 i 或者 j 有一個為 0，i-1 或 j-1 則為負數，所以初始值需要先計算出所有 i 或 j 為 0 的情況。

var minDistance = function (word1, word2) {
  const m = word1.length,
    n = word2.length
  const dp = new Array(m).fill(0).map((_) => new Array(n).fill(0))
  dp[0][0] = 0

  for (let i = 1; i <= m; i++) {
    dp[i][0] = dp[i - 1][0] + 1
  }

  for (let j = 1; j <= n; j++) {
    dp[0][j] = dp[0][j - 1] + 1
  }

  for (let i = 1; i <= m; i++) {
    for (let j = 1; j <= n; j++) {
      // 注意第 i 個字符的下標是 i-1
      if (word1[i - 1] === word2[j - 1]) {
        dp[i][j] = dp[i - 1][j - 1]
      } else {
        dp[i][j] = Math.min(dp[i - 1][j - 1], dp[i][j - 1], dp[i - 1][j]) + 1
      }
    }
  }
  return dp[m][n]
}

console.log(minDistance('horse', 'ros')) // 3