05｜面试即正义第一期：什么样的问题应该使用动态规划？

作者回复: 总结的很对，顶上去让跟多人看到。

作者回复: 举个例子，给定一个数组 [2, 3, 1, 6, 7]，如果要求最长上升子串，我们该怎么求呢？ 需要做排列组合，找到最长的那个吧？那么如果数据“可交换”，会发生什么？ 如果我们把数组重新排序，那么原问题也就不复存在了。所以当原问题可以重新排序时，那么那个问题不用动态规划来解，因为不需要穷举。 比如说，我们还是上面的数组作为输入，但问的问题是数组中最大值是什么？那么你可以先排序，然后取开头或结尾的值，就是你要的答案了。 这里想强调说明的是，并非看到数组或字符串问题都需要使用动态规划来求解。也许朴素的算法能更快得到解。

作者回复: 字符串的动态规划是特定的一类动态规划问题，这类问题在后面的子数组和子序列问题中会详细讲解，并给出求解模板和套路。 建议阅读参考一下。

作者回复: 这跟状态参数的定义是有极大关系的。在后面讲解12课动态规划新问题2的时候，你就会发现即便是子数组问题，也需要高维备忘录来存储中间计算的过程。 具体问题具体分析。因此，简单的子数组问题可以认为只需要一维数组作为备忘录就可以解决问题；子序列问题一般需要高维数组作为备忘录解决问题。 但这不是绝对的。在学习了后面的思路分析和解题步骤后，相信你会有新的认识。

作者回复: 但是一般路径规划不会考虑重复走过同一个节点，所以这里性质还是不太一样的。

作者回复: 这个是在特定场景下可以用特殊设计的贪心算法来解决问题，但是这种思路无法解决更多的问题，所以我们才需要学习如何通过动态规划解决问题，这也是使用动态规划解决的最简单的一类问题了。

作者回复: 请阅读一下 06 和 07 课针对背包问题的完整阐述。 在讲解完全背包的部分，里面有详细的讲解。