peanut的小铺

Appearance

动态规划 ​

概念 ​

动态规划（英语：Dynamic programming，简称 DP），是一种在数学、管理科学、计算机科学、经济学和生物信息学中使用的，通过把原问题分解为相对简单的子问题的方式求解复杂问题的方法。动态规划常常适用于有重叠子问题和最优子结构性质的问题。

简单来说，动态规划其实就是，给定一个问题，我们把它拆成一个个子问题，直到子问题可以直接解决。然后呢，把子问题答案保存起来，以减少重复计算。再根据子问题答案反推，得出原问题解的一种方法。

动态规划最核心的思想，就在于拆分子问题，记住过往，减少重复计算。

思路 ​

  1. 确定状态转移方程

  2. 不同规模的相同问题之间的关系

寻找状态转移方程的一般性步骤 ​

  1. 找到相同问题（重叠子问题），相同问题必须适配不同的规模

  2. 找到重叠子问题之间的关系

  3. 找到重叠子问题的特解

实现 ​

例子 1：斐波拉契数列 ​

1 1 2 3 5 8 13

如dp(n)= dp(n-1) + dp(n-2)

js
function dp(n) {
  if (n === 1 || n === 2) {
    return 1
  }
  return dp(n - 1) + dp(n - 2)
}
dp(3) // 2
dp(4) // 3
function dp(n) {
  if (n === 1 || n === 2) {
    return 1
  }
  return dp(n - 1) + dp(n - 2)
}
dp(3) // 2
dp(4) // 3

在实际场景中，斐波拉契数列的 n 很大，递归会导致爆栈，因此需要进行特殊优化，将前面遍历过程中的计算结果提前存起来

js
let memoMap = new Map()

var fib = function (n) {
  if (n < 2) {
    return n
  }
  if (memoMap.has(n)) {
    return memoMap.get(n)
  }
  let first = fib(n - 1)
  let second = fib(n - 2)
  let result = first + second
  memoMap.set(n, result)
  return result
}
let memoMap = new Map()

var fib = function (n) {
  if (n < 2) {
    return n
  }
  if (memoMap.has(n)) {
    return memoMap.get(n)
  }
  let first = fib(n - 1)
  let second = fib(n - 2)
  let result = first + second
  memoMap.set(n, result)
  return result
}

例子 2：青蛙跳台阶问题 ​

青蛙从底部跳到 n 级台阶，可以 1 次跳 1 级或者 1 次跳 2 级，有多少种跳法。

状态转移方程可以这么考虑，假如只有 6 级台阶，那么根据上一次的情况，有 2 种情况可以跳到第 6 级：

  1. 第 5 级，跳 1 级

  2. 第 4 级，跳 2 级

往前推导，第 5 级和第 4 级也是各有 2 种情况可以跳上来，这两种情况是递归的关系

因此我们可以得到状态转移方程如下

js
dp(6) = dp(5) + dp(4)
dp(6) = dp(5) + dp(4)

仍然是斐波拉契数列

例子 3: 不同路径 ​

机器人在棋盘上只能向右或向下移动，从左上角(0,0)到右下角(i,j)有多少条路径？

  1. 确定相同问题和适应不同规模的表达式：

dp(i, j) // 到达第 i 行第 j 列有多少条路径

  1. 找到子问题之间的关系
js
dp(i, j) = dp(i - 1, j) + dp(i, j -1)
dp(i, j) = dp(i - 1, j) + dp(i, j -1)
  1. 找到特殊解

当i === 0 || j === 0时，dp(i, j) === 1

得到状态转移方程

js
// dp(i, j) = dp(i - 1, j) + dp(i, j - 1)
let dpMap = new Map()

var uniquePaths = function (m, n) {
  const dp = (i, j) => {
    let key = `${i}-${j}`
    let result
    if (dpMap.get(key)) {
      return dpMap.get(key)
    }
    if (i === 0 || j === 0) {
      result = 1
    } else {
      result = dp(i - 1, j) + dp(i, j - 1)
    }
    dpMap.set(key, result)
    return result
  }
  return dp(m - 1, n - 1)
}
// dp(i, j) = dp(i - 1, j) + dp(i, j - 1)
let dpMap = new Map()

var uniquePaths = function (m, n) {
  const dp = (i, j) => {
    let key = `${i}-${j}`
    let result
    if (dpMap.get(key)) {
      return dpMap.get(key)
    }
    if (i === 0 || j === 0) {
      result = 1
    } else {
      result = dp(i - 1, j) + dp(i, j - 1)
    }
    dpMap.set(key, result)
    return result
  }
  return dp(m - 1, n - 1)
}

解法二：生成一个数组，返回最后一行的最后一列的数字

js
// dp(i, j) = dp(i - 1, j) + dp(i, j - 1)
var uniquePaths = function (m, n) {
  const dp = []
  for (let i = 0; i < m; i++) {
    dp.push([])
    for (let j = 0; j < n; j++) {
      if (i === 0 || j === 0) {
        dp[i][j] = 1
      } else {
        dp[i][j] = dp[i - 1][j] + dp[i][j - 1]
      }
    }
  }
  return dp[m - 1][n - 1]
}
// dp(i, j) = dp(i - 1, j) + dp(i, j - 1)
var uniquePaths = function (m, n) {
  const dp = []
  for (let i = 0; i < m; i++) {
    dp.push([])
    for (let j = 0; j < n; j++) {
      if (i === 0 || j === 0) {
        dp[i][j] = 1
      } else {
        dp[i][j] = dp[i - 1][j] + dp[i][j - 1]
      }
    }
  }
  return dp[m - 1][n - 1]
}