[Coursera] Design and Analysis of Algorithm, Part 2 [Week 3]

Shuang7 发表于 2013-9-26 05:40
嗯这好像就是coursera论坛里面大家讨论bottom-up和top-down的含义？我还以为一个是从A(1,0)算到A(1,m)和A ...

那递归和DP都是一个性质，为什么第二题递归会快？
递归每次还要调用函数，要压栈出栈，不应该更费时么

圆梦梦剧场 发表于 2013-9-26 11:32
那递归和DP都是一个性质，为什么第二题递归会快？
递归每次还要调用函数，要压栈出栈，不应该更费时么

我猜还是递归避免了一些无用的计算，这里的无用指的是对最终结果没有影响的运算，比如A(0,m)到A(n-1,m)似乎都没用，因为它们都不影响结果，我们只需要A(n,m) ?

Shuang7 发表于 2013-9-27 06:19
我猜还是递归避免了一些无用的计算，这里的无用指的是对最终结果没有影响的运算，比如A(0,m)到A(n-1,m)似 ...

递归也计算了A(0,m)到A(n-1,m)的。至少我写的递归我觉得是要计算到的。和DP一样都把A(n,m)给计算满了

圆梦梦剧场 发表于 2013-9-27 08:52
递归也计算了A(0,m)到A(n-1,m)的。至少我写的递归我觉得是要计算到的。和DP一样都把A(n,m)给计算满了

所以你应该修改一下不算那些没用的东西？
不知道里面有没有被抛掉的没有计算的东西，我的意思是矩阵的中间部分。

Shuang7 发表于 2013-9-27 13:50
所以你应该修改一下不算那些没用的东西？
不知道里面有没有被抛掉的没有计算的东西，我的意思是矩阵的中 ...

版主你第二问是用DP还是递归的？
我觉得用递归也必须计算所有A(n,m)的
我去看看coursera上人家的思路

圆梦梦剧场 发表于 2013-9-27 16:19
版主你第二问是用DP还是递归的？
我觉得用递归也必须计算所有A(n,m)的
我去看看coursera上人家的思路

没有用递归，最近时间紧来不及仔细琢磨。。你加油~有消息了告诉我下:)

第二周的作业已经错过deadline了……

圆梦梦剧场 发表于 2013-9-24 21:14
嗯，那其实也可以用一个2*M的数组或者M的数组来cache。
那我感觉DP和用了cache的递归是一个意思，只不过 ...

对的，DP 就是 bottom-up，循环是从 index= 0 写起的，每一个 size = n 的问题构建在 size = n-1 的基础上。

cached recursive 也就是 memoization，属于 top-down 的设计，调用时从 n 开始，往下计算。cache的作用是避免重复计算。

asterid 发表于 2013-9-28 14:36
对的，DP 就是 bottom-up，循环是从 index= 0 写起的，每一个 size = n 的问题构建在 size = n-1 的基础上 ...

嗯，那既然计算量一样，都是计算了一个N*M的两位数组，为什么第二题递归会快呢？
递归每次还要调用函数，要压栈出栈，不应该更费时么

圆梦梦剧场 发表于 2013-9-28 03:03
嗯，那既然计算量一样，都是计算了一个N*M的两位数组，为什么第二题递归会快呢？
递归每次还要调用函数， ...

Recursive 应该可以避免一些不必要的 subproblem 的计算，类似于 depth-first search，没用的路径不探索。而 DP 类似 breadth-first search，同一层所有的 subproblem 都要展开。

不过这题我没用 DP，也不知道具体怎样。
补充一下，这是从 stackoverflow（http://stackoverflow.com/questio ... dynamic-programming） 上看来的，概括得非常清楚：

• If all subproblems must be solved at least once, a bottom-up dynamic-programming algorithm usually outperforms a top-down memoized algorithm by a constant factor
  • No overhead for recursion and less overhead for maintaining table
  • There are some problems for which the regular pattern of table accesses in the dynamic-programming algorithm can be exploited to reduce the time or space requirements even further
    
• If some subproblems in the subproblem space need not be solved at all, the memoized solution has the advantage of solving only those subproblems that are definitely required