动态规划

简介

动态规划方法通常用来求解最优化问题，这类问题可以有很多可行解，每个解都有一个值，我们希望寻找具有最优值（最小值或最大值）的解。通常按一下四个步骤来设计一个动态规划算法：

• 刻画一个最优解的结构特征
• 递归地定义最优解的值
• 计算最优解的值，通常采用自底向上的方法
• 利用计算出的信息构造一个最优解

相较于带备忘（缓存计算结果）的自顶向下的递归算法，动态规划没有频繁的递归函数调用的开销，因此在时间复杂性上通常小一些。

问题解法

1. 判断是否符合动态规划的特征

• 重叠子问题：判断在穷举的过程中是否存在重复计算的问题？
• 无后效性：判断后续的选择是否会对前面的计算产生副作用？e
• 最优子结构：判断后续的计算是否可以通过前面的状态推导出来？

2. 写出状态转移方程

• 初始化状态：边界条件
• 状态参数：影响计算的关键参数
• 状态方程：决策 - 子问题之间的关系，如：Dp[i][j] = Math.max([Dp[i][j-1], Dp[i-1][j])

3. 根据状态转移方程编码

实例：背包问题

问题

给你一个可放总重量为 W 的背包和 N 个物品，对每个物品，有重量 w 和价值 v 两个属性，那么第 i 个物品的重量为 w[i] ，价值为 v[i]。现在让你用这个背包装物品，问 最多能装的价值是多少？

// 创建二维数组
const createTwoDimensionalArray = (x = 0, y = 0, fill = 0) => {
  return (new Array(x)).fill(0).map(() => {
    return new Array(y).fill(fill)
  })
}

// 背包总重
const W = 5
const N = 3
const wight = [0, 3, 2, 1]
const value = [0, 5, 4, 1]

const bag = (w, v, N, W) => {
  const dp = createTwoDimensionalArray(N + 1, W + 1)
  // 遍历每一个物品
  for (let n = 1; n <= N; n++) {
    // 背包容量有多大就要计算多少次
    for (let rw = 1; rw <= W; rw++) {
      if (w[n] > rw) {
        // 如果当前物品重量大于背包剩余重量，只能放入 n - 1件物品
        dp[n][rw] = dp[n - 1][rw]
      } else {
        // 如果当前物品重量小于背包剩余重量，进一步决策（包含该物品/不包含该物品）
        dp[n][rw] = Math.max(dp[n - 1][rw - w[n]] + v[n], dp[n - 1][rw])
      }
    }
  }
  return dp[N][W]
}

console.log(bag(wight, value, N, W)) // 9

实例：完全背包问题

问题

给你一个可放总重量为 W 的背包和 N 个物品，对每个物品，有重量 w 和价值 v 两个属性，那么第 i 个物品的重量为 w[i] ，价值为 v[i]。现在让你用这个背包装物品，每种物品都可以选择任意多个，问最多能装的价值是多少？

相较于0和1背包问题，完全背包问题的物品可以被多次选择。基本思路大致相同：

// 当第n个物品的重量超过剩余重量的时候，取n-1个物品时的最大价值
if (w[n] > rw) {
	dp[n][rw] = dp[n - 1][rw]
}

// 当第n个物品重量小于剩余重量时，循环放入第n个物品，取它们的最大值
// max(dp[n - i][rw - w[n] * i] + w[n] * i); (条件为 0 <= i <= n）

在循环取第n个物品的时候，存在重复计算的问题，如求解rw - w[n] * 1的时候，实际上会求解rw - w[n] * 2、rw - w[n] * 3等情况。因此状态方程可以优化为：

// 不取第 n 个物品，使用 n - 1 的值
dp[n - 1][rw]
// 取第 n 个物品
w[n] + dp[n][rw - w[n]]
// 结合起来就是：
max(dp[n - 1][rw], w[n] + dp[n][rw - w[n]])

这样就少了一层的循环，在时间复杂度上得到了优化。另外，由于第n行的数据只依赖于第n-1行的数据，那么在用备忘录缓存的时候只需要用2个数组（代替二维数组）记录数据即可，这样就可以优化空间复杂度的目的。

实例：子数组问题

问题

给定一个整数数组 nums ，找到一个具有最大和的连续子数组（子数组最少包含一 个元素），返回其最大和。

const arr = [-2, 1, -3, 4, -1, 3, -5, 1, 2]

const maxSumOfSubArray = (arr) => {
  // dp 内保存着 包含最后一个元素的连续子数组 的最大和
  const dp = new Array(arr.length).fill(0)
  let max = dp[0]
  for (let i = 1; i < arr.length; i++) {
    // 判断是否需要重新更改数组的起始位置
    dp[i] = Math.max(dp[i - 1] + arr[i], arr[i])
    // 与前面的最大值进行比较
    max = Math.max(dp[i], max)
  }
  return max
}

console.log(maxSumOfSubArray(arr)); // 6

实例：不重叠子数组之和问题

问题

给定一个整数数组 nums 和一个整数 k，找出 k 个不重叠子数组使得它们的和最大，每个子数组的数字在数组中的位置应该是连续的，返回其最大和。

首先结果是与数组的索引和k相关，因此可以创建一个二维备忘录dp[i][k]。当遍历到第i个元素时，有如下情况：

// 数组里不包含第 i 个元素，因此采用 i - 1 的最大值
dp[i - 1][k]
// 数组里包含第 i 个元素，又因为数组是连续的，所以最后一个数组可能包含 i/i-1/i-2...个元素这些情况
max(dp[i - j][k - 1] + sum(j, i)) 其中 0 <= j <= i

在“数组里包含第 i 个元素”这种情况下，每次计算实际上都会使用到以i结尾划分为k个数组的数组和。另外创建一个备忘录m[i][k]记录和:

// 一种是 i - 1 划分了 k - 1 个组
m[i - 1][k - 1] + nums[i]
// 一种是 i - 1 划分了 k 个组，第k个组与 i 接壤，及形成第 k 组,
// 此时也可能 i - 1 的第 k 个组最后一个组不包含 i - 1个元素
// 因此是两者取最大值
max(m[i-1][k], dp[i - 1][k - 1]) + nums[i]

实例：子序列问题

问题

给定一个字符串 s ，找到其中最长的回文子序列，并返回该序列的长度。

const s = 'asssasms'

const getLongestPalindromeSubseq = (s) => {
  const n = s.length
  const dp = createTwoDimensionalArray(n, n, 0)
  // 对角线上 i === j, 此时长度为1
  for (let k = 0; k < n; k++) {
    dp[k][k] = 1
  }
  for (let i = n - 1; i >= 0; i--) {
    for (let j = i + 1; j < n; j++) {
      if (s[i] === s[j]) {
        // 如果相等，则为内部的长度 + 2
        dp[i][j] = dp[i + 1][j - 1] + 2
      } else {
        // 如果不相等，则进一步决策
        dp[i][j] = Math.max(dp[i][j - 1], dp[i + 1][j])
      }
    }
  }
  return dp[0][n - 1]
}

console.log(getLongestPalindromeSubseq(s)) // 5

实例：最长连续递增子序列问题

问题

给定一个未经排序的整数数组 nums，找到最长的连续递增序列，并返回该序列的长度。

// 当遍历到第 i 个元素时
// 如果不包含第 i 个元素，取 i - 1 个元素的最大值
dp[i - 1]
// 如果包含第 i 个元素，循环比较 i - 1, i - 2 ...
// 如果第 j 个元素大于第 i 个元素，此时不为递增，取dp[j]
// 如果第 j 个元素小于第 i 个元素，此时递增，取 dp[j] + 1
// 然后取最大值最终循环的最大值

应用场景

• 求“最”优解问题（最大值和最小值），如最长回文字符串
• 求可行性（true 或 false），如凑零兑换
• 求方案总数，如背包
• 数据不可排序，如子序列

参考

• 极客时间 - 动态规划面试宝典