最优子结构原理和 dp 数组遍历方向
原创动态规划核心框架约 3872 字
Info
已完成网站教程、网站习题、配套插件中所有多语言代码的校准，解决了之前 chatGPT 翻译可能出错的问题~
Tip
本文有视频版：动态规划详解进阶。建议关注我的 B 站账号，我会用视频领读的方式带大家学习那些稍有难度的算法技巧。
本文是旧文 动态规划答疑篇 的修订版，根据我的不断学习总结以及读者的评论反馈，我给扩展了更多内容，力求使本文成为继 动态规划核心套路框架 之后的一篇全面答疑文章。以下是正文。
这篇文章就给你讲明白以下几个问题：
1、到底什么才叫「最优子结构」，和动态规划什么关系。
2、如何判断一个问题是动态规划问题，即如何看出是否存在重叠子问题。
3、为什么经常看到将 dp 数组的大小设置为 n + 1 而不是 n。
4、为什么动态规划遍历 dp 数组的方式五花八门，有的正着遍历，有的倒着遍历，有的斜着遍历。