动态规划是什么？

小榛鼠

可以说说你们的理解吗

981013

动态规划背后的基本思想非常简单。大致上，若要解一个给定问题，我们需要解其不同部分（即子问题），再合并子问题的解以得出原问题的解。

通常许多子问题非常相似，为此动态规划法试图仅仅解决每个子问题一次，从而减少计算量：一旦某个给定子问题的解已经算出，则将其记忆化（en:memoization）存储，以便下次需要同一个子问题解之时直接查表。这种做法在重复子问题的数目关于输入的规模呈指数增长时特别有用。引自Wiki百科

可见，动归就是在满足：
1.对某个问题，可以通过解决其规模稍小的子问题来解决（分治，要求最优子结构和无后效性）
2.分解出的子问题中存在重复的子问题（重叠子问题）
时，通过：
1.对问题进行分解
2.解决子问题（如果某个子问题还没有被解决，那就解决它并将结果放入一张表中，如果这个子问题已经被解决过了就直接在表中读取结果）
3.利用子问题的结果装配出最终答案
来解决问题的一种思路。
我们以计算斐波那契数列为例：
根据斐波那契数列的定义，数列的第n(n≥2)项【为方便起见，称为f(n)]是数列的第n-1项和n-2项的和】，那么问题就可以分解成求f(n-1)和f(n-2)两个子问题，这就是问题的分解
然后我们可以发现，在计算f(n-1)的递归树上，需要用到从f(0)到f(n-2)的每一个值，而在计算f(n-2)时，需要用到f(0)到f(n-3)的每一个值，它们已经在计算前面的“从f(0)到f(n-2)的每一个值”中被计算过了！所以实际上两棵递归树上有很多节点的计算是重复的。这就是所谓的重叠子问题。因此不如用一张表保存已经被计算出来的f值，以后调用f时，先查表，若表中有对应的值就直接采用表中的结果，没有的话再进行计算，并将结果放入表中。这就避免了重复解决子问题。
最后给出同样来自wiki的伪代码
[mw_shl_code=c,true]array map [0...n] = { 0 => 0, 1 => 1 }
fib（n）
    if（map m does not contain key n）
        m[n] := fib(n − 1) + fib（n − 2）
    return m[n][/mw_shl_code]
另外，动态规划和递推在很多情况下确实可以互相替代，但是递推反应的是一种从最小的子问题开始，一点一点用小的子问题的答案来推更大的子问题的答案，直到原问题被解决，是一种自底而上的想法。动归则是从问题本身开始，逐步分解为小一些的（有重复的）子问题，直到问题可以被容易地解决，是一种自顶而下的想法。

4399APPLE

我可以从哪里来      

小榛鼠

实话说我是真的一点都不了解，
我是经常看到你回答“这不就是DP吗？”
所以想说这到底是啥，是种算法？是种解题的方法？还是一种思路？
有没可能说个大概范围，概念或者举个例子？
深入的我了解了以后会再提问，或者我应该再去补些什么知识再来问？

小榛鼠

我是自学，没人带，喜欢的部分就去看，不喜欢的就跳过，
也没什么目标，所以学的乱七八糟的，先说声谢谢指导了

邀请码

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

4399APPLE

小榛鼠 发表于 2016-8-28 11:59
实话说我是真的一点都不了解，
我是经常看到你回答“这不就是DP吗？”
所以想说这到底是啥，是种算法？是 ...

一种思路               

4399APPLE

邀请码 发表于 2016-8-28 12:54
在絮叨之前，我得说一句，这不就是DP吗？
我记得之前我有个帖子说“用已求得的值求新值得编程方法”叫动态 ...

其实数字三角形是个递推不是DP。。。

邀请码

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

然而我把它当成dp看了TaT

小榛鼠

觉得DP和递推还蛮难分的..

小榛鼠

这个贴子过几天在结，希望能知道更多大家的看法，谢谢两位

邀请码

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

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

981013

邀请码 发表于 2016-8-29 19:26
Wikipedia说的很好，不过伪代码我看不懂

给段C吧
[mw_shl_code=c,true]#include <stdio.h>
#define MAX 10
int cache[MAX]={0,1};
int fib(int n) {
    if(cache[n] != -1)                  //已经缓存了fib(n)
        return cache[n];                //直接返回缓存的值
    int result = fib(n-1) + fib(n-2);
    cache[n] = result;                  //更新缓存
    return result;
}
int main(int argc, const char * argv[]) {
    //初始化所有数字的结果为未计算
    for (int i=2; i<MAX; ++i)           //如果你的编译器不支持C99（如啊哈C的默认状态），请将int i提前
        cache = -1;
    printf("%d\n",fib(9));
    return 0;
}
[/mw_shl_code]
PS:状态转移方程和数列前项后项之间的关系式差不多。

4399APPLE

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

但是我总感觉Fib是递推QaQ

邀请码

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

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