精读《算法 - 动态规划》

[ascoders]

前端精读进入算法篇，原文来源很多，有一些我看的网上视频课，也有刷过的算法题，总之希望对大家理解算法有帮助！

---

精读《算法 - 动态规划》

[baxtergu]

个人理解：动态规划 是一种算法的更高抽象，其本质在于利用 规律 来跳过无意义的重复计算，进而达到时间复杂度降低的目的。这其中最难的部分就在于 找规律，就像初阶奥数题一样，如果这个规律你知道了，基于类似规律的题目就可以很容易的解答；但是，如果这个规律没有接触过，那么这个过程会很漫长，甚至会做出题目无法使用 动态规划 给出题解的结论。

比如文章中提到：

• 栅栏刷油漆的这题，dp[i] = (dp[i-1]+dp[i-2])*(k-1) 这个结论还是比较容易得出的。因为就算是没有dp的概念，这个规律只需要向前推进2个元素就可以得到
• Dom diff 中最上上升子序列就比较难了，需要对 dp[0] ~ dp[i-1] 做 max 操作，这些思维具有一定的跳跃性，很难在没有解过类似规律算法题目的情况下快速找到规律
• 像是有效括号的题目：需要对 dp[0] ~ dp[i-1] 做更复杂条件运算，门槛就更高了。

所以我觉得 动态规划 更多的考的是经验的储备（动态规划所有模式的刷题量），而不是真正的实际场景解决问题的能力。