dynamic programming 啥意思

看到programming指的当然是编程，就不想看了...

youlegelin 发表于 2020-11-20 07:03:46
我觉得动态规划就是家里老人们口中的“走一步看一步”哈哈

走一步看一步那是贪心，dp正好相反啊...

补充内容 (2020-12-4 21:34):
dynamic就是想对于static（也就是走一步看一步）的啊

youlegelin 发表于 2020-11-20 23:03
我觉得动态规划就是家里老人们口中的“走一步看一步”哈哈

走一步看一步是gready。。。会陷入local minimum

其实对于一个问题，如果用“穷举”的方法解，就是DFS。
如果在穷举过程中有一些state是重复的，那我们就能记录下他们，下次就不用重复计算。
所以DP可以看成DFS的优化。关键要找出哪些state是重复的，就是所谓的找到状态转移方程

在我没怎么学过编程和算法的时候的，我看到dp先想到的是数学， bellman function。。。。。

动态 这个翻译没错啊 ，变动的状态- - 典型的例子就是很多人说经典的普林斯顿算法4那本书没有DP（包括中文版本的前言里也说没有dp），实际上是功夫没到家，那本书就是用状态机来解释String和regular expression，这就是正了八经的动态规划的思想。只不过我们习惯用Array来表示而已。

"... the essence of dynamic programming: Multistage problems may be solved by analyzing a sequence of simpler inductively defined single-stage problems."

Martin L. Puterman, Markov decision processes: discrete stochastic dynamic programming. John Wiley & Sons, 2014.