動的計画法 - Sayyiku

動的計画法の 3 つのステップ#

動的計画法は、重複する計算を避けるために、過去の記録を利用することです。そして、これらの記録を保存するために、一次元配列または二次元配列を使用します。

ステップ 1：配列要素の意味を定義する。 過去の記録を保存するために、一般的には一次元配列 dp[] を使用します。この時、各配列要素の意味は非常に重要です。

ステップ 2：配列要素間の関係式を見つける。 動的計画法は、高校で学んだ帰納法に似ており、dp[n-1]、dp[n-2]...dp[1] を利用して dp[n] を導くことができます。つまり、過去のデータを利用して新しい要素の値を導くことができるため、配列要素間の関係式を見つける必要があります。例えば、dp[n] = dp[n-1] + dp[n-2] がその関係式です。

ステップ 3：初期値を見つける。 配列要素間の関係式がわかっても、dp[n] を導くためには初期値が必要です。

カエルの跳ねる台#

カエルは 1 段または 2 段飛ぶことができます。n 段の台を飛ぶための方法は何通りありますか？

配列要素の意味を定義する：n 段の台に飛ぶ方法は、dp[i] 通りあります。私たちの目標は dp[n] を求めることです。
配列要素間の関係式を見つける：この問題では、カエルは 1 段飛ぶか 2 段飛ぶかを選ぶことができるため、カエルが i 段目の台に到達する方法は 2 つあります。1 つは i-1 段目から飛び上がる方法で、もう 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×n のグリッドの左上にいます。ロボットは常に下または右に 1 ステップ移動することができます。ロボットはグリッドの右下に到達しようとしています。異なる経路の総数はいくつですか？

配列要素の意味を定義する：グリッドを二次元配列と見なし、始点の座標を (0,0)、右下の座標を (m-1)(n-1) とします。ロボットが (i,j) の位置に到達する方法の数をdp[i][j]とします。したがって、私たちの目標はdp[m-1][n-1]を求めることです。
配列要素間の関係式を見つける：(i,j) の位置に到達する方法は 2 つあります。1 つは (i-1,j) の位置から到達する方法で、もう 1 つは (i,j-1) の位置から到達する方法です。したがって、すべての到達方法はdp[i][j] = dp[i-1][j] + dp[i][j-1]です。
初期値を見つける：i=0 または j=0 の場合、右または下にしか移動できないため、方法は 1 つだけです。

求解コード：

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×n のグリッドが与えられます。ロボットは常に下または右に 1 ステップ移動することができます。左上の角から右下の角までのパスの数字の合計が最小になるパスを見つけてください。

配列要素の意味を定義する：グリッドを二次元配列と見なし、始点の座標を (0,0)、右下の座標を (m-1)(n-1) とします。左上の角から (i,j) の位置に到達する最小経路和をdp[i][j]とします。したがって、私たちの目標はdp[m-1][n-1]を求めることです。
配列要素間の関係式を見つける：(i,j) の位置に到達する方法は 2 つあります。1 つは (i-1,j) の位置から到達する方法で、もう 1 つは (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 の場合、右または下にしか移動できないため、最小経路和も 1 つだけです。

求解コード：

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 の合計が最小

編集距離#

問題の出典：編集距離

2 つの単語 word1 と word2 が与えられた場合、word1 を word2 に変換するために必要な最小操作回数を返します。次の 3 つの操作を行うことができます：

文字の挿入

文字の削除

文字の置換

配列要素の意味を定義する：文字列 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] が等しくない場合、3 つの操作があります。これらの操作の最小値を見つける必要があります。したがって、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 は負の数になるため、初期値を計算する必要があります。

求解コード：

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