动态规划

注意

不懂动态规划的话，很难从一篇文章就学会动态规划，对不理解动态规划的人解释动态规划本身也很不容易。所以请看完后自己做题深入理解。

例题

举例使用较为常用的“连续子数组的最大和”

输入: nums = [-2,1,-3,4,-1,2,1,-5,4]
输出: 6
解释: 连续子数组 [4,-1,2,1] 的和最大，为 6。

找出拆分方法和每步最优解

例子里 [-2,1,-3,4,-1,2,1,-5,4]，我打算计算出每一步的“连续最大和”，要做到这件事，先整一个 dp 列表。

Q：dp 列表是个什么？

A：每一格都放着那一步的“连续最大和”

接着，循环遍历每一个新增的元素，研究这个元素对整个 dp 列表有什么影响。求其中关系的方程被称为“状态转移方程”。

for (let i = 1; i < nums.length; i++) {
  dp[i] = Math.max(nums[i], nums[i] + dp[i - 1])
}

Q：为什么 i 从 1 开始

A：0 是特殊情况，在循环前设置 dp = [nums[0]]

注意知与未知

第 i 个值依赖于 i - 1 的值，所以需要从小到大循环，因为 i - 1 需要在 i 之前确定，

同样的原理，若是 i 依赖 i + 1 的话，需要从大到小循环。

注意答案需要的是什么

上面也说了，dp 数组存的是每一步的“连续最大和”，而问题是求连续最大和，也就是，找出 dp 数组中的最大值。

var maxSubArray = function (nums) {
    dp = [nums[0]]
    max = nums[0]
    for (let i = 1; i < nums.length; i++) {
        dp[i] = Math.max(nums[i], nums[i] + dp[i - 1])
        max = Math.max(max,dp[i])
    }
    return max
};

动态规划只是一种思路

就像你知道递归，依然不一定很轻易能搞定使用递归的算法，前面三步在一些难题中依然需要花费大量时间