有哪些资源可以更好的帮助理解动态规划(DP)问题？

[tesorouo]

感觉很难理解，而且经常弄不清哪些情况是可以用动态规划解决

[Herobs]

首先是最经典的背包问题，然后结合 DFS 来一起理解，都可以解决同一个问题，只不过方向不一样，最后再回头看动态规划那几个特征的涵义。

[newtype0092]

推荐《背包九讲》，虽然主要讲背包问题，但看懂了以后其实大部分 DP 问题都能转化到背包问题。

[ChanKc]

Introduction to Algorithms, third edition

[msg7086]

动规要开窍，开窍了就通了。
我小时候听人讲动规，比如经典问题最长单调串，一直没搞懂怎么回事。
后来突然有一天想通了，就懂了。

一般来说，只要能尝试写出状态转移方程就能搞明白了。
换句话说，假定你知道某个小问题的解，然后去推算一个更大问题的解。
比如说背包，假定你想知道背包重量为 10 的解，有一个物品重量为 2，那么他的解就是重量为 8 的时候的最优解加上物品 2 的价值。
比如说最长单调串，假定你想知道长度为 10 的字符串的最大单调长度，那么你可以取前 9 个元素的长度，再额外判断多出来的那一个元素，就能得到新的解。

已知 N 元素的最优解，通过简单方法可得 N+1 元素的最优解，这种问题就都可以用 DP 来做。

[tesorouo]

都很有帮助，感谢大家，欢迎继续推荐