这是一个创建于 1565 天前的主题，其中的信息可能已经有所发展或是发生改变。
感觉很难理解，而且经常弄不清哪些情况是可以用动态规划解决
 |
1
Herobs 2020-07-17 18:29:35 +08:00 via iPhone  1
首先是最经典的背包问题，然后结合 DFS 来一起理解，都可以解决同一个问题，只不过方向不一样，最后再回头看动态规划那几个特征的涵义。
|
 |
2
newtype0092 2020-07-17 18:41:04 +08:00 1
推荐《背包九讲》，虽然主要讲背包问题，但看懂了以后其实大部分 DP 问题都能转化到背包问题。
|
 |
3
ChanKc 2020-07-17 18:45:40 +08:00 1
Introduction to Algorithms, third edition
|
 |
4
msg7086 2020-07-18 02:27:54 +08:00 1
动规要开窍，开窍了就通了。
我小时候听人讲动规，比如经典问题最长单调串，一直没搞懂怎么回事。 后来突然有一天想通了，就懂了。 一般来说，只要能尝试写出状态转移方程就能搞明白了。 换句话说，假定你知道某个小问题的解，然后去推算一个更大问题的解。 比如说背包，假定你想知道背包重量为 10 的解，有一个物品重量为 2，那么他的解就是重量为 8 的时候的最优解加上物品 2 的价值。 比如说最长单调串，假定你想知道长度为 10 的字符串的最大单调长度，那么你可以取前 9 个元素的长度，再额外判断多出来的那一个元素，就能得到新的解。 已知 N 元素的最优解，通过简单方法可得 N+1 元素的最优解，这种问题就都可以用 DP 来做。 |
 |
5
tesorouo OP 都很有帮助，感谢大家，欢迎继续推荐
|
Select Language