BlogAbout
Published on

动态规划真的好难...

Authors

动态规划是一种通过把原问题分解为相对简单的子问题的方式求解复杂问题的方法，它不是一种具体的算法，而是一种解决特定问题的方法。

三要素

能用动态规划解决的问题，需要满足三个条件：

  • 最优子结构

    简单说就是：一个问题的最优解包含子问题的最优解。

    注意：最优子结构不是动态规划方法独有的，也可能适用贪心。

  • 重叠子问题

    子问题之间会有重叠，参考斐波那契数列，求 f(5) 依赖于 f(4)fn(3), f(4) 依赖于 f(3)f(2)。如果有大量的重叠子问题，我们可以用空间将这些子问题的解存储下来，避免重复求解相同的子问题，从而提升效率。

  • 无后效性

    已经求解的子问题，不会再受到后续决策的影响。

// 每个节点只能向左下或者向右下走一步
        7
      3   8
    8   1   0
  2   7   4   4
4   5   2   6   5

从顶到底，最大和路径 7 -> 3 -> 8 -> 7 -> 5。

依次来看：

  • 每一层都会有最优解，且就是那一层所有子问题的最优解 --- 满足最优子结构

  • 每一层的最优解不会因为下一层的选择而发生改变 --- 满足无后效性；

  • 这道题倒是没有类似斐波那契类似的交叉的子问题，没有重叠子问题

    （注意不是依赖于上一层的最优解，那就变成贪心了。 比如 第二层最优为 7-8，但是第三层是 7-3-8。）

基本思路

对于一个能用动态规划解决的问题，一般采用如下思路解决：

  1. 将原问题划分为若干阶段，每个阶段对应若干个子问题，提取这些子问题的结果即「状态」；
  2. 寻找每一个状态的可能「决策」，或者说是各状态间的相互转移方式（用数学的语言描述就是「状态转移方程」）。
  3. 按顺序求解每一个阶段的问题。

如果用图论的思想理解，我们建立一个 有向无环图，每个状态对应图上一个节点，决策对应节点间的连边。这样问题就转变为了一个在 DAG 上寻找最长（短）路的问题。

练一练

序列 dp

lc.1143 最长公共子序列

思考：

原问题是从 a、b 两个字符串寻找最长公共子序列，那么子问题就是 a、b 字符串的子串之间的最长公共子序列，比如 a[0] 和 b[0]，往前推的子问题可能是 a[0-1] 和 b[0]、a[0] 和 b[0-1]、a[0-1]和 b[0-1]等等，每一个子问题的结果都是一个「状态」

稍微有点经验后，一般应对两两比较类的动态规划，可以使用双指针进行子问题推进，也就是使用二维 dp 数组去解决。

精练一下：

  • 「状态」：定义 dp[i][j] 表示**A 的前 i 个元素，B 的前 j 个元素**的最长公共子序列的长度，这样每一个 dp[i][j] 都表示了一个状态。

    注意：通常将dp[i]定义为表示前i个元素的状态，更容易处理边界情况，例如 dp[0]通常被定义为初始状态，表示空集或空字符串对应的状态。

  • 「决策」：每一个 dp[i][j]都有 3 个决策：
    1. a[i] == b[j]，dp[i][j] = dp[i-1][j-1] + 1
    2. a[i] != b[j]，dp[i][j] = Math.max(dp[i-1][j] + dp[i][j-1]) ，两个决策中选择较大的那个

      注意：这里的 a[i]、b[j] 的 i,j 只是指针游走，表示第 i、j 个，(实际位置应当是 a[i-1]、b[j-1])，方便状态推导，与 dp 的前 i,j 个相呼应。根据分析, dp[i-1][j-1]一定小于等于 dp[i-1][j]或 dp[i][j-1]

/**
 * @param {string} text1
 * @param {string} text2
 * @return {number}
 */
var longestCommonSubsequence = function (text1, text2) {
    const m = text1.length
    const n = text2.length
    const dp = Array.from(Array(m + 1), () => Array(n + 1).fill(0))
    // base case 分别 a 串为 0 或 b 串为 0 的情况，在初始化时已经处理。一般也可以分别 for 循环搞定
    for (let i = 1; i <= m; ++i) {
        for (let j = 1; j <= n; ++j) {
            if (text1[i - 1] === text2[j - 1]) {
                dp[i][j] = dp[i - 1][j - 1] + 1
            } else {
                dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1])
            }
        }
    }
    return dp[m][n]
}

lc.1035 不相交的线，与本题基本一模一样。

lc.300 最长递增子序列

做过上题，再做这题，很容易写出如下代码：

var lengthOfLIS = function (nums) {
    /** 定义 dp[i] 表示前 i 个元素的最长递增子序列的长度*/
    const dp = Array.from(Array(nums.length + 1), () => 0)
    // dp[0] = 0
    dp[1] = 1
    for (let i = 2; i <= nums.length; ++i) {
        if (nums[i - 1] > nums[i - 2]) {
            dp[i] = dp[i - 1] + 1
        } else {
            dp[i] = dp[i - 1]
        }
    }
    return dp[nums.length]
}

很遗憾的是，这么做是错的，问题在 nums[i - 1] > nums[i - 2] 只是和前一个元素比较，而 nums[0..i-1] 之间最长的递增子序列不一定是 nums[0..i-1]，有可能是 nums[0..i-2]等等，所以如此定义 dp 数组的含义，状态转移方程是有问题的，应当与之前的每一个元素进行比较，然后更新最大的。

那么，请看另一种定义：dp[i] 表示以 nums[i] 结尾的最长递增子序列，且 nums[i-1] 必须被选上

/**
 * @param {number[]} nums
 * @return {number}
 */
var lengthOfLIS = function (nums) {
    /**
     * 定义： dp[i] 表示**以 nums[i] 结尾**的最长递增子序列的长度
     * 注意： nums[i] 必须选中
     */
    const n = nums.length
    const dp = Array(n).fill(1) // 长度至少为 1，即其自身
    for (let i = 1; i < n; ++i) {
        // 应当与之前的每一个元素进行比较
        for (let j = 0; j < i; ++j) {
            if (nums[i] > nums[j]) {
                // nums[i] 必选
                dp[i] = Math.max(dp[i], dp[j] + 1)
            }
        }
    }
    return Math.max(...dp)
}

这道题进阶，将时间复杂度降到 O(nlogn)，这基本上就是在暗示使用二分法了，还是有点挑战的。

// TODO 二分+贪心

lc.354 俄罗斯套娃信封问题就是基于此题，只不过需要稍微转变一下思路：要保证对于每一种 w 值，我们最多只能选择 1 个信封，所以对 w 升序排序，当 w 相等时，对 h 降序排序。且这道题只能使用二分+贪心的方式求最长递增子序列，否则会超时。

lc.674 最长连续递增子序列

重点在于连续递增~，此时，就不用和 i 之前的每个元素比了，只用和前一个比，但是定义依然是 dp[i] 表示以 nums[i] 为选中元素的最长递增子序列的长度 😂

/**
 * @param {number[]} nums
 * @return {number}
 */
var findLengthOfLCIS = function (nums) {
    const n = nums.length
    /** 定义 dp[i] 表示以 nums[i] 结尾的最长连续递增子序列的长度 */
    const dp = Array(n).fill(1)
    for (let i = 1; i < n; ++i) {
        if (nums[i] > nums[i - 1]) {
            dp[i] = dp[i - 1] + 1
        }
    }
    return Math.max(...dp)
}

lc.392 判断子序列 easy

判断字符串 a 是否是 b 的子序列。这很明显用双指针就能搞得定。

var isSubsequence = function (s, t) {
    let i = 0,
        j = 0
    while (i < s.length && j < t.length) {
        if (s[i] === t[j]) {
            i++
        }
        j++
    }
    return i === s.length
}

此处为了使用动态规划而动态规划一下🐶，a 是 b 的子序列，则 a 和 b 的最长公共子序列就是 a 的长度~

/**
 * @param {string} s
 * @param {string} t
 * @return {boolean}
 */
var isSubsequence = function (s, t) {
    const m = s.length
    const n = t.length
    const dp = Array.from(Array(m + 1), () => Array(n + 1).fill(0))
    for (let i = 1; i <= m; ++i) {
        for (let j = 1; j <= n; ++j) {
            if (s[i - 1] === t[j - 1]) {
                dp[i][j] = dp[i - 1][j - 1] + 1
            } else {
                dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1])
            }
        }
    }
    return s.length === dp[m][n]
}

lc.115 不同的子序列 hard

字符串 s 和 t ，统计并返回在 s 的 子序列 中 t 出现的个数。

需要动一下脑筋，举例思考，abb 和 ab，定义 dp[i][j] 表示 a 的前 i 个字符的子序列包含 b 的前 j 个字符的个数

  • 当 a[i] == b[i] 时
    • 若使用 a[i]，则 dp[i][j] = dp[i-1][j-1]
    • 若不使用 a[i]，则 dp[i][j] = dp[i-1][j]
  • 当 a[i] != b[i] 时，dp[i][j] = dp[i-1][j]
/**
 * @param {string} s
 * @param {string} t
 * @return {number}
 */
var numDistinct = function (s, t) {
    const m = s.length
    const n = t.length
    const dp = Array.from(Array(m + 1), () => Array(n + 1).fill(0))
    // 这道题需要格外注意 base case
    for (let i = 0; i <= m; ++i) {
        dp[i][0] = 1 // 当 t 为 0 的时候，总能包含一次~
    }
    for (let i = 1; i <= m; ++i) {
        for (let j = 1; j <= n; ++j) {
            if (s[i - 1] == t[j - 1]) {
                dp[i][j] = dp[i - 1][j - 1] + dp[i - 1][j] // 相同就用+不用
            } else {
                dp[i][j] = dp[i - 1][j] // 不同就不用
            }
        }
    }
    return dp[m][n]
}

lc.53 最大子数组和

/**
 * @param {number[]} nums
 * @return {number}
 */
var maxSubArray = function (nums) {
    const n = nums.length
    // 定义 dp[i] 表示以 nums[i] 结尾的的最大连续子数组的和
    const dp = Array(n)
    dp[0] = nums[0]
    for (let i = 1; i < n; ++i) {
        // 决策是 +nums[i] 与 nums[i] 自身比较，如果还没 nums[i] 大，那么就 nums[i] 自成一派即可
        dp[i] = Math.max(dp[i - 1] + nums[i], nums[i])
    }
    return Math.max(...dp)
}

lc.718 最长重复子数组

/**
 * @param {number[]} nums1
 * @param {number[]} nums2
 * @return {number}
 */
var findLength = function (nums1, nums2) {
    // 定义 dp[i][j] 表示nums1前 i 和 nums2 前 j 个最长的子数组的长度
    // 且第 i 个和第 j 个必须选上
    let res = 0
    const m = nums1.length
    const n = nums2.length
    const dp = Array.from(Array(m + 1), () => Array(n + 1).fill(0)) // 覆盖了dp[0][0] dp[i][0] dp[0][j] 都为 0
    for (let i = 1; i <= m; ++i) {
        for (let j = 1; j <= n; ++j) {
            // i-1,j-1 位置必须选上，否则就为 0，初始化时已经覆盖
            if (nums1[i - 1] === nums2[j - 1]) {
                dp[i][j] = dp[i - 1][j - 1] + 1
                res = Math.max(res, dp[i][j])
            }
        }
    }
    return res
}

lc.72 编辑距离 hard

这道题以前是 hard~ 🐶 简单分析一下 word1 -> word2，可以增删改，求最少操作数。（就问你烦不烦吧 🌧）

仔细分析下来，你会发现，此题和 lc.1143 有异曲同工之处，差别不是很大。

两个字符串，少不了两个指针，定义 dp[i][j] 表示 a 前 i 个转为 b 前 j 个字符串使用的最少操作数。

至于决策，相比 lc.1143 多了一个罢了，每个状态都有 4 种决策：

  1. a[i] === b[j]，dp[i][j] = dp[i-1][j-1]，不需要操作
  2. a[i] !== b[j]，dp[i][j] = Math.min(a 插，a 删，a 改) + 1

    再次强调：这里的 a[i]、b[j] 的 i,j 只是指针游走，表示第 i、j 个，(实际位置应当是 a[i-1]、b[j-1])，方便状态推导，与 dp 的前 i,j 个相呼应。

问题来了，当 a[i] != b[j] 时，a 插，a 删，a 改，怎么用 dp 表示呢？说实话需要点思考。

  • a 插，dp[i][j-1] + 1，在 a[i] 后插入一个和 b[j] 相同的字符，a[i+1]把 b[j]抵消了，此时就需要看 a[i] 转为 b[j-1]的最小步骤了，此时要让 a == b 则就需要看 a[1:i] 转换为 b[1:j-1]的最小步骤了，即 dp[i][j-1]
  • a 删，dp[i-1][j] + 1，删除 a[i]，即看 a[1:i-1] 转换为 b[1:j]的最小步骤。
  • a 改，dp[i-1][j-1] + 1，换一个字符只需要看 a[1:i-1] 转换为 b[1:j-1]
/**
 * @param {string} word1
 * @param {string} word2
 * @return {number}
 */
var minDistance = function (word1, word2) {
    const m = word1.length
    const n = word2.length
    // 定义 dp[i][j] 表示 A 的前 i 个转为 B 的前 j 个元素所用的最小步骤
    const dp = Array.from(Array(m + 1), () => Array(n + 1).fill(0))
    // base case
    for (let i = 0; i <= m; ++i) {
        dp[i][0] = i
    }
    for (let j = 0; j <= n; ++j) {
        dp[0][j] = j
    }
    for (let i = 1; i <= m; ++i) {
        for (let j = 1; j <= n; ++j) {
            if (word1[i - 1] == word2[j - 1]) {
                dp[i][j] = dp[i - 1][j - 1]
            } else {
                dp[i][j] = Math.min(dp[i][j - 1], dp[i - 1][j], dp[i - 1][j - 1]) + 1
            }
        }
    }
    return dp[m][n]
}

lc.583 两个字符串的删除操作

搞懂 lc.72，那么这道题就是小 case 的啦~

/**
 * @param {string} word1
 * @param {string} word2
 * @return {number}
 */
var minDistance = function (word1, word2) {
    // 定义 dp[i][j] 表示 word1 前 i 个 -> word2 前 j 个 的最小步数
    const m = word1.length
    const n = word2.length
    const dp = Array.from(Array(m + 1), () => Array(n + 1).fill(0))
    for (let i = 1; i <= m; ++i) {
        dp[i][0] = i
    }
    for (let j = 1; j <= n; ++j) {
        dp[0][j] = j
    }

    for (let i = 1; i <= m; ++i) {
        for (let j = 1; j <= n; ++j) {
            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], dp[i][j - 1]) + 1 // 做删 word1 或者删 word2 的选择
            }
        }
    }
    return dp[m][n]
}

经验

做到这里，可以发现，目前对于序列/字符串 dp 的定义一般有两种：

  1. dp[i] 表示前 i 个...
  2. dp[i] 表示以 el[i] 结尾...

最后，再来两道略微不一样的题。

lc.516 最长回文子序列

定义 dp[i][j] 表示 s[i:j] 之间的最大回文串的长度(闭区间)。一个常识：怎么判断区间 s[i:j] 是否为一个回文串，从两头往中间，看是否相等。

所以：

  • a[i] == a[j] 时，dp[i][j] = dp[i+1][j-1] + 2
  • a[i] != a[j] 时，dp[i][j] = Math.max(dp[i+1][j], dp[i][j-1])

注意：当出现 i 依赖于 i + 1 的情况，就需要分析一下遍历的方式。首先根据定义，i < = j, base case 就是对角线；根据状态转移方程每个节点都是从左边和下边推导上来的，如下图 1；由此可以脑补出二位矩阵图，如下图 2。

遇到上图 2 的情况，可以斜着遍历（虚线），当然也可以从下往上&从左往右这样子遍历。

/**
 * @param {string} s
 * @return {number}
 */
var longestPalindromeSubseq = function (s) {
    const len = s.length
    const dp = Array.from(Array(len), () => Array(len).fill(0))
    // base case 自身一定为回文串
    for (let i = 0; i < len; ++i) {
        dp[i][i] = 1
    }
    // 根据状态转移公式，确定遍历方法，可以倒着遍历（简单就不演示了），
    // 也可以斜着遍历，此处采用斜着遍历
    // 从左往右数第2根线开始遍历，因为第一根线已经都确定了
    for (let l = 2; l <= len; ++l) {
        for (let i = 0; i <= len - l; ++i) {
            // 关键获取 j 坐标，右上半区的 i，j 坐标与 l 的关系:
            // l 就是闭区间 [i,j] 的长度，因此可以得出 j = l + i - 1
            const j = l + i - 1
            if (s[i] === s[j]) {
                dp[i][j] = dp[i + 1][j - 1] + 2 // 相同的情况下, 收缩 长度+2
            } else {
                dp[i][j] = Math.max(dp[i + 1][j], dp[i][j - 1]) // 比较选择[i+1..j] 和[i..j-1]中较大的那个
            }
        }
    }
    return dp[0][len - 1]
}

lc.1312 让字符串成为回文串的最少插入次数 hard

一个重要的思路：让字符串成为回文串的最少插入次数，等价于原字符长度减去最长回文子串的长度。如果想不到这一点，那确实挺难的。

/**
 * @param {string} s
 * @return {number}
 */
var minInsertions = function (s) {
    const n = s.length
    const dp = Array.from(new Array(n), _ => new Array(n).fill(0))
    // base case
    for (let i = 0; i < dp.length; ++i) {
        dp[i][i] = 1
    }
    for (let l = 2; l <= n; ++l) {
        for (let i = 0; i <= n - l; ++i) {
            let j = l + i - 1
            if (s[i] === s[j]) {
                dp[i][j] = dp[i + 1][j - 1] + 2
            } else {
                dp[i][j] = Math.max(dp[i + 1][j], dp[i][j - 1])
            }
        }
    }
    return n - dp[0][n - 1]
}

小结

总的来说，序列 dp 类的问题，不是很难，只要多思考，状态转移方程还是挺容易找得到的，奥利给 💪🏻。

背包 dp

背包类问题，可以学习前人的总结---背包九讲-崔添翼，十分详尽，初级阶段，先掌握好基础的「01 背包」「完全背包」和「多重背包」问题吧 💪🏻。

01 背包

01 背包是背包问题的基础中的基础，完全背包和多重背包都可以转换为 01 背包问题。

  • 问题：N 个物品， V 容量的背包。放入第 i 个物品至背包，占用 Wi 的容量，获得 Ci 的价值。
  • 特点：每个物品都只有一件，选择放或者不放。
  • 状态定义及转移：dp[i][v] 表示前 i 个物品放入 v 容量背包能获得的最大价值。
    • 不放，dp[i][v] = dp[i-1][v]，容量不变，价值与放入前一个一致
    • 放入，dp[i][v] = Math.max(dp[i-1][v - wi] + ci, dp[i-1][v])，放入则需要与不放入进行比较，因为能放入的容量为 v-wi，需要找到能放入前的最大价值再加上 ci 即放入的最大价值。
空间复杂度优化

⭐️：空间压缩的核心思路就是，将二维数组「投影」到一维数组

单就 01 背包的二维状态转移方程来看 dp[i][v] = Math.max(dp[i-1][v - wi] + ci, dp[i-1][v])，i 只与 i-1 有关，那么就可以这么干：dp[v] = Math.max(dp[v], dp[v-wi] + ci)。需要理解的是：

在 dp[v] 还未被赋值时：

  1. 右侧的 dp[v] 是外层 for 循环上一次迭代出的结果。在这里对应着 dp[i-1][v]。
  2. 右侧的 dp[v-wi] 如果内层 for 循环是顺序遍历，则是表示内层 for 循环的结果 dp[i][v-wi]，这显然是与二维方程所违背的，因此，内层遍历背包的时候需要倒序才能拿到上一轮外循环的结果，否贼就会被覆盖。举例：假设 dp[10] 依赖于 dp[6]，如果是顺序，则 dp[6] 会先于 dp[10]更新，导致 dp[10] 无法得到上一轮迭代的 dp[6]。

进一步了解空间压缩，上面做过的最长回文子序列的状态转移方程为 dp[i][j] = Math.max(dp[i+1][j], dp[i][j-1]) || dp[i+1][j-1] + 2，dp[i][j] 依赖于三个状态，那么投影干掉 i 维度后:

  • a[i] == a[j]: dp[j] = dp[j-1] + 2
  • a[i] != a[j]: dp[j] = Math.max(dp[j], dp[j-1])

此时，右侧的 dp[j] 表示的是上一轮外层 for 循环的结果，即 dp[i+1][j]，由于是顺序遍历，dp[j-1] 表示的是内层 for 循环的结果，即 dp[i][j-1]，那么就剩下 dp[i + 1][j - 1] 还没有结果，那是因为二维变一维的时候，它的值被 dp[i][j-1] 覆盖掉啦（想象从上往下投影），解决办法也很简单，类似普通的交换方法中的技巧，先暂存起来不就好了 ☀️！

/**
 * ！！！PS：斜着遍历不便于理解空间压缩，使用倒着遍历比较好理解~~~
 */
var longestPalindromeSubseq = function (s) {
    var n = s.length
    // base case：一维 dp 数组全部初始化为 1
    var dp = new Array(n).fill(1)
    // 从倒着遍历二维 i，来处理较为轻松
    for (var i = n - 2; i >= 0; i--) {
        var pre = 0
        for (var j = i + 1; j < n; j++) {
            var temp = dp[j]
            // 状态转移方程
            if (s.charAt(i) == s.charAt(j)) {
                dp[j] = pre + 2
            } else {
                dp[j] = Math.max(dp[j], dp[j - 1])
            }
            pre = temp
        }
    }
    return dp[n - 1]
}
lc.416 分割等和子集
/**
 * @param {number[]} nums
 * @return {boolean}
 */
var canPartition = function (nums) {
    const sum = nums.reduce((t, v) => t + v)
    if (sum % 2 !== 0) return false
    const target = sum / 2 // 背包
    const n = nums.length
    // 定义前 i 个元素可以装满容量为 j 的背包
    const dp = Array.from(Array(n + 1), () => Array(target + 1).fill(false))
    for (let i = 0; i <= n; ++i) dp[i][0] = true
    for (let i = 1; i <= n; ++i) {
        for (let j = 1; j <= target; ++j) {
            if (nums[i - 1] > j) {
                dp[i][j] = dp[i - 1][j]
            } else {
                dp[i][j] = dp[i - 1][j] || dp[i - 1][j - nums[i - 1]]
            }
        }
    }
    return dp[n][target]
}

此题的巧妙之处在于没有真的去累加选择元素的值，而是直接根据 Boolean 状态的传递来判断的。

lc.474 一和零

普通 01 背包只有一个容量限制，这题有 2 个，分别是 0 和 1 的数量，因此可以预想到时间复杂度要高一些，但总体思想还是一致的。

/**
 * @param {string[]} strs
 * @param {number} m
 * @param {number} n
 * @return {number}
 */
var findMaxForm = function (strs, m, n) {
    // 定义 dp[i][j][k] 表示 前 i 个元素，含 j 个 0 和 k 个 1 的最大子集数
    const len = strs.length
    const dp = Array.from(Array(len + 1), () =>
        Array(m + 1)
            .fill(0)
            .map(_ => Array(n + 1).fill(0))
    )
    for (let i = 1; i <= len; ++i) {
        const el = strs[i - 1]
        const oneCount = el.split('').filter(_ => _ == '1').length
        const zeroCount = el.length - oneCount
        for (let j = 0; j <= m; j++) {
            for (let k = 0; k <= n; ++k) {
                if (j < zeroCount || k < oneCount) {
                    dp[i][j][k] = dp[i - 1][j][k]
                } else {
                    dp[i][j][k] = Math.max(
                        dp[i - 1][j][k],
                        dp[i - 1][j - zeroCount][k - oneCount] + 1
                    )
                }
            }
        }
    }
    return dp[len][m][n]
}
lc.494 目标和

这道题比较绝~，第一反应应该是回溯。

var findTargetSumWays = function (nums, target) {
    let res = 0
    const backtrack = (index, sum) => {
        if (index === nums.length) {
            if (sum === target) {
                res++
            }
        } else {
            backtrack(index + 1, sum + nums[index])
            backtrack(index + 1, sum - nums[index])
        }
    }
    backtrack(0, 0)
    return res
}

再来看一下动态规划，讲道理，第一时间我是真的想不到。。。需要先做一个数学推导：

集合总体可以分为 A、B 两个子集，那么就有：

  • A - B = target
  • A + B = sum

因此 2A = sum + target，A = (sum + target) >> 1；如此一来就巧妙地转变为了 lc.416 分割等和子集的问题了~~~

定义 dp[i][j] 表示前 i 个元素构造运算结果为 j 的不同表达式数目

var findTargetSumWays = function (nums, target) {
    const n = nums.length
    const sum = nums.reduce((t, v) => t + v)
    if (Math.abs(target) > sum || (sum + target) % 2 !== 0) return 0 // 注意需要对 target 去绝对值
    const goal = (sum + target) / 2
    // 定义 dp[i][j] 表示前 i 个元素构造运算结果为 j 的不同表达式数目
    const dp = Array.from(Array(n + 1), () => Array(goal + 1).fill(0))
    // 特殊 base case
    dp[0][0] = 1 // 不考虑任何数，凑出计算结果为 0 的方案数为 1 种。
    for (let i = 1; i <= n; ++i) {
        for (let j = 0; j <= goal; ++j) {
            if (nums[i - 1] > j) {
                dp[i][j] = dp[i - 1][j]
            } else {
                dp[i][j] = dp[i - 1][j] + dp[i - 1][j - nums[i - 1]] // 能选择选
            }
        }
    }
    return dp[n][goal]
}
1049. 最后一块石头的重量 II

该题可以抽象为将 n 块石头分为两堆，而后求两堆石头重量总和的最小差值。 因此便可看为 01 背包问题，背包最大容量为这 n 块石头总重量的一半 那么理想情况下，如果可以刚好装满背包，两堆石头重量总和的最小差值便可为零。

/**
 * @param {number[]} stones
 * @return {number}
 */
var lastStoneWeightII = function (stones) {
    const n = stones.length
    const sum = stones.reduce((t, v) => t + v)
    const target = sum >> 1
    // 定义 dp[i][j] 表示前 i 个元素，容量为j的背包所能存放的实际最大值
    const dp = Array.from(Array(n + 1), () => Array(target + 1).fill(0))
    for (let i = 1; i <= n; ++i) {
        for (let j = 0; j <= target; ++j) {
            if (stones[i - 1] > j) {
                dp[i][j] = dp[i - 1][j]
            } else {
                dp[i][j] = Math.max(dp[i - 1][j - stones[i - 1]] + stones[i - 1], dp[i - 1][j]) // 放或不放最大值
            }
        }
    }
    return sum - dp[n][target] * 2
}

可以看到有些问题是 01 背包的变种问题，掌握住核心思想，拓展思维（其实得多练，不然 👻 能想得到啊 😭）

完全背包

  • 问题：N 种物品， V 容量的背包。放入第 i 种物品至背包，占用 Wi 的容量，获得 Ci 的价值。
  • 特点：每种物品有无数件，选择不再是选货不选，而且选 0、1、2...直到 V/Wi 次。
  • 状态定义及转移：dp[i][v] 表示前 i 种物品恰放入一个容量为 v 的背包的最大价值，类似 01 背包可以给出基础方程：dp[i][v] = Math.max(dp[i-1][v], dp[i-1]v-k*wi] + k*ci )，0 <= kwi <= v。然而，这样求解每个状态的时间复杂度就不是常数级了，来到了O(v/wi)，总的时间复杂度是 O(NVΣV/Ci)，是比较高的，所以一般都需要优化。
空间复杂度优化

⭐️ 巧的是：完全背包的 O(NV) 的状态转移方程，与 01 背包的一维状态转移方程几乎一样，唯一的不同是内层不需要倒着遍历了~~~ 01 背包倒着遍历，是为了保证拿到上一轮的 dp[v-wi]，完全背包则无需这个保证。

不过我个人并不推荐上来直接就写一维方程，会比较难以理解，写熟练之后可以这么干

lc.139 单词拆分

字典中的单词可以重复使用，每个单词也只有选择用和不用，完全背包问题，分析出这个，后面就简单了：

/**
 * @param {string} s
 * @param {string[]} wordDict
 * @return {boolean}
 */
var wordBreak = function (s, wordDict) {
    // 完全背包排列问题，定义 dp[j] 表示s前 i 个字符，可以由单词组成
    const n = s.length
    const dp = Array(n + 1).fill(false)
    dp[0] = true
    for (let i = 0; i <= n; i++) {
        for (let j = 0; j < i; j++) {
            // ! 重点 j表示分割 状态转移方程看s[0..j-1]和s[j..i-1] 是否都合法
            if (dp[j] && wordDict.includes(s.substring(j, i))) {
                dp[i] = true
                break
            }
        }
    }
    return dp[n]
}
lc.279 完全平方数

动态规划 定义 dp[i] 表示数字 i 的完全平方数最少。

/**
 * @param {number} n
 * @return {number}
 */
var numSquares = function (n) {
    const dp = Array(n + 1).fill(0)
    for (let i = 0; i <= n; ++i) {
        dp[i] = i // 最差每次+1
        for (let j = 1; j * j <= i; ++j) {
            dp[i] = Math.min(dp[i], dp[i - j * j] + 1)
        }
    }
    return dp[n]
}
lc.322 零钱兑换

求组合成 target 使用物品最少数

/**
 * @param {number[]} coins
 * @param {number} amount
 * @return {number}
 */
var coinChange = function (coins, amount) {
    // 经典完全背包题目，定义 dp[i] 表示不同面额组合成 i 的最少硬币个数
    const dp = Array(amount + 1).fill(amount + 1) // 肯定不会超过 amount + 1
    dp[0] = 0
    for (let i = 0; i <= amount; ++i) {
        for (const coin of coins) {
            if (coin > i) {
                continue
            } else {
                dp[i] = Math.min(dp[i], dp[i - coin] + 1)
            }
        }
    }
    return dp[amount] === amount + 1 ? -1 : dp[amount]
}
lc.518 零钱兑换 II

相比上一题，本题求的是填满背包物品组合的问题的，一定是先遍历物品再遍历背包。

/**
 * @param {number} amount
 * @param {number[]} coins
 * @return {number}
 */
var change = function (amount, coins) {
    const n = coins.length
    const dp = Array(amount + 1).fill(0)
    dp[0] = 1
    for (let i = 0; i < n; ++i) {
        for (let j = coins[i]; j <= amount; ++j) {
            dp[j] = dp[j] + dp[j - coins[i]]
        }
    }
    return dp[amount]
}
lc.377 组合总和 Ⅳ

不要被题目名欺骗了，看题目，是一道赤裸裸的排列问题。。。

/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number}
 */
var combinationSum4 = function (nums, target) {
    const dp = Array(target + 1).fill(0)
    dp[0] = 1
    for (let j = 0; j <= target; ++j) {
        for (let i = 0; i < nums.length; ++i) {
            if (nums[i] <= j) {
                dp[j] = dp[j] + dp[j - nums[i]]
            }
        }
    }
    return dp[target]
}

多重背包

多重背包和完全背包相比，就是限定每种物品的数量为 Mi。

70.爬楼梯

/**
 * @param {number} n
 * @return {number}
 */
var climbStairs = function (n) {
    // 1. 定义 dp[i]: 表示爬到第 i 层时的方法数为 dp[i]，第n层 索引为 n + 1
    // 所以初始化为 Array(n + 1)
    const dp = new Array(n + 1).fill(0)
    // 2. 根据题 初始化
    dp[1] = 1
    dp[2] = 2
    // 3. 确定递归公式, 到达第 i 层，可以从i-1层或i-2层进入,
    // 所以方法数为这两种到达第i层的和: dp[i-1] + dp[i-2]
    // 4. 由于i 依赖于 i-1,i-2 所以要从前往后遍历
    for (let i = 3; i < dp.length; ++i) {
        dp[i] = dp[i - 1] + dp[i - 2]
    }
    return dp[n]
}

746.使用最小花费爬楼梯

/**
 * @param {number[]} cost
 * @return {number}
 */
var minCostClimbingStairs = function (cost) {
    // 1. 定义dp[i]: 表示到达第 i 层花费的最小值, 要求的是 dp[cost.length]
    // 所以定义 dp 容量为 cost.length + 1
    const n = cost.length
    const dp = new Array(n + 1).fill(0)
    // 2. 初始化 根据题 可以从 0 或 1 下标开始 dp[0]=dp[1]=0
    dp[0] = 0
    dp[1] = 0
    // 3. 公式 dp[i] = min(dp[i-1] + cost[i-1], dp[i-2] + cost[i-2])
    for (let i = 2; i <= n; ++i) {
        dp[i] = Math.min(dp[i - 1] + cost[i - 1], dp[i - 2] + cost[i - 2])
    }
    return dp[n]
}

上方两种题比较，70 题是过程中推到，相对容易；746 题是目标极值推导，对于新手而言要相对难一点，当然了，如果对动规每个细节都烂熟于心，那都很 easy 啦~👻

62.不同路径

有点算法基础的人，回过头来再看这道题，乍一看，是不是好像要用回溯或者 dfs？ --还真可以，但是！时间复杂度将是指数级的！(将一个 2*2 的矩阵转为二叉树就能很容易理解了，就是求叶子节点的个数)

我的感觉是（不一定对哈，欢迎留言讨论），题目出给了提示：只能向右或向下，这是在提示我们可以做「选择」，那么就可以联想到用动态规划去做了。👻

/**
 * @param {number} m
 * @param {number} n
 * @return {number}
 */
var uniquePaths = function (m, n) {
    // 1. 定义dp[i][j]: 表示从matrix[0][0]到达 matrix[i][j]的总共路径
    const dp = Array.from(new Array(m), _ => new Array(n).fill(0))
    // 2. base case i == 0 / j == 0 的边界条件 dp[0][j] = 1 dp[j][0] = 1
    for (let i = 0; i < m; ++i) dp[i][0] = 1
    for (let j = 0; j < n; ++j) dp[0][j] = 1
    // 3. 递推公式 [i][j] 可以从 [i-1][j] 或者 [i][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]
}

63.不同路径 II

/**
 * @param {number[][]} obstacleGrid
 * @return {number}
 */
var uniquePathsWithObstacles = function (obstacleGrid) {
    // 定义dp[i][j]: [0][0] 到 [i][j] 的路径总数
    const m = obstacleGrid.length
    const n = obstacleGrid[0].length
    const dp = Array.from(new Array(m), _ => new Array(n).fill(0))
    // base case
    dp[0][0] = obstacleGrid[0][0] === 1 ? 0 : 1
    for (let i = 1; i < m; ++i) dp[i][0] = obstacleGrid[i][0] === 1 ? 0 : dp[i - 1][0]
    for (let j = 1; j < n; ++j) dp[0][j] = obstacleGrid[0][j] === 1 ? 0 : dp[0][j - 1]
    // 递推公式: 没啥难的,就是考虑一下障碍物嘛
    // dp[i][j] = 0 || dp[i-1][j] + dp[i][j-1]
    for (let i = 1; i < m; ++i) {
        for (let j = 1; j < n; ++j) {
            dp[i][j] = obstacleGrid[i][j] === 1 ? 0 : dp[i - 1][j] + dp[i][j - 1]
        }
    }
    return dp[m - 1][n - 1]
}

343.整数拆分

这道题和路径一样，一眼看上去好像就要搞出所有的结果集然后对比，就得用 dfs 或者回溯，但是显然，这种是不靠谱的。

这道题给出的提示是：最大乘积！求极值--这就是一种选择，可以 dfs 出所有的结果，那么动态规划就值得一试！

/**
 * @param {number} n
 * @return {number}
 */
var integerBreak = function (n) {
    // 定义 dp[i]: 表示 数字 i 的最大乘积 (2<=n<=58)
    const dp = new Array(n + 1).fill(0)
    // base case
    dp[2] = 1
    // 这道题的难点就是推导公式--》最大乘积怎么获得? -- 拆分! 有拆分就有选择啦
    // i 拆分为一个数 j 和 i-j, 乘积为 i*(i-j), 1 <= j < i
    // i-j 继续拆分，i*dp[i-j]
    for (let i = 3; i <= n; ++i) {
        for (let j = 1; j < i; ++j) {
            dp[i] = Math.max(j * (i - j), j * dp[i - j], dp[i])
        }
    }
    return dp[n]
}

感兴趣的建议看官方题解，可以利用数学知识得到最优解，时间复杂度 O(1)，很有意思。

如开头所讲，动态规划之时一种解决方法，更是一种思路，题型和题目杂而多，本文只是对动态规划有一个初步的概念，想要熟练掌握，还是得多刷题多思考啊，peace！

推荐阅读

View on GitHub