最优子结构原理和 dp 数组遍历方向

本文是旧文 动态规划答疑篇 的修订版，根据我的不断学习总结以及读者的评论反馈，我给扩展了更多内容，力求使本文成为继 动态规划核心套路框架 之后的一篇全面答疑文章。以下是正文。

这篇文章就给你讲明白以下几个问题：

1、到底什么才叫「最优子结构」，和动态规划什么关系。

2、如何判断一个问题是动态规划问题，即如何看出是否存在重叠子问题。

3、为什么经常看到将 dp 数组的大小设置为 n + 1 而不是 n。

4、为什么动态规划遍历 dp 数组的方式五花八门，有的正着遍历，有的倒着遍历，有的斜着遍历。