动态规划是什么？

邀请码

在絮叨之前，我得说一句，这不就是DP吗？
我记得之前我有个帖子说“用已求得的值求新值得编程方法”叫动态规划，然而这个说法其实我觉得挺对的。。
就拿最简单的数字三角形说，每一次取得的值都用到了上一次取得的值，而一些其它方法只是用到了输入的值。
再比如说记忆化搜索，每次都看看之前是否求过了这次搜索的值，否则只用搜索一次数组一存，一劳永逸。
那么可以说是动态规划“省了时间，废了空间”

邀请码

4399APPLE 发表于 2016-8-28 13:03
其实数字三角形是个递推不是DP。。。

然而我把它当成dp看了TaT

邀请码

981013 发表于 2016-8-29 17:24
可见，动归就是在满足：
1.对某个问题，可以通过解决其规模稍小的子问题来解决（分治，要求最优子结构和 ...

Wikipedia说的很好，不过伪代码我看不懂

邀请码

4399APPLE 发表于 2016-9-6 21:04
但是我总感觉Fib是递推QaQ

我一直把dp和递推当成一个玩意儿来看待，就是学不会的玩意儿