动态规划一定要有Optimal Substructure吗？ - 未名空间MITBBS历史存档

国际科技财经博客移民网络热点娱乐民生时事公众号

Redian新闻

>未名空间

>JobHunting - 待字闺中

动态规划一定要有Optimal Substructure吗？

动态规划一定要有Optimal Substructure吗？# JobHunting - 待字闺中

z*j2014-03-29 07:03

1 楼

RT， dynamic programming is a method for solving complex problems by
breaking them down into simpler subproblems. It is applicable to problems
exhibiting the properties of overlapping subproblems[1] and optimal
substructure.
重叠子问题很好理解，但是，能够应用于DP解决的问题一定要有optimal substructure
吗？就好比Fibonacci所谓的DP解法，只是用了个memo记录下了之间计算过得结果以避
免子问题的重复计算，但是貌似看不出有什么最优子结构啊。求指点...

g*x2014-03-29 07:03

2 楼

最有子结构是个概念
你把问题divide成很多小的，分别求最优，然后合并起来
但问题是，合并起来的不一定是最优的
你要证明合并起来的也是最优的=> optimal substructure

V*r2014-03-29 07:03

3 楼

能写出Bellman递推等式的就有optimal substructure，fib那个递归式就是
规避重复计算靠的是overlapping subproblems

substructure

【在 z****j 的大作中提到】

: RT， dynamic programming is a method for solving complex problems by
: breaking them down into simpler subproblems. It is applicable to problems
: exhibiting the properties of overlapping subproblems[1] and optimal
: substructure.
: 重叠子问题很好理解，但是，能够应用于DP解决的问题一定要有optimal substructure
: 吗？就好比Fibonacci所谓的DP解法，只是用了个memo记录下了之间计算过得结果以避
: 免子问题的重复计算，但是貌似看不出有什么最优子结构啊。求指点...

s*u2014-03-29 07:03

4 楼

如果你想求得最优解的话是必须的了，如果只是想sub-optimal的话可以track sub-
problem的optimality gap in a tolerated range.

l*n2014-03-29 07:03

5 楼

楼主应该不是要解最优化问题,而是在做coding题

z*j2014-03-29 07:03

6 楼

我明白你说的意思，但像fibonacci那个dp的解法一样，overlapping substructure很
明显，但是却看不出有什么Optimal substructure？但是为什么还划在了DP的范畴，换
句话就是optimal substructure是DP的必要条件么？

【在 g***x 的大作中提到】

: 最有子结构是个概念
: 你把问题divide成很多小的，分别求最优，然后合并起来
: 但问题是，合并起来的不一定是最优的
: 你要证明合并起来的也是最优的=> optimal substructure

z*j2014-03-29 07:03

7 楼

我只是好奇optimal substructure是DP的必要条件么？换句话说能够应用DP的问题一定
要有optimal substructure么？

【在 l******n 的大作中提到】

: 楼主应该不是要解最优化问题,而是在做coding题

z*j2014-03-29 07:03

8 楼

可能是我理解有点问题... 不过像fib（n） = fib（n-1） + fib（n-2）这样的递归式
它的optimal点体现在哪里呢？这个也可以算是optimal substructure吗

【在 V*********r 的大作中提到】

: 能写出Bellman递推等式的就有optimal substructure，fib那个递归式就是
: 规避重复计算靠的是overlapping subproblems
:
: substructure

J*a2014-03-29 07:03

9 楼

opt的意思不是“最优解法”，optimal不是你想的算法复杂度最优的“优”
而是正确解的意思
比如背包问题，背包体积为W，那么W能放下的最大价值为OPT（W）
那这个OPT（W）表示的其实是背包体积为W时的“正确解”
同理，你找出了OPT（W）和OPT（W-1）、OPT（W-2）.。。的关系之后就可以解这题了
这里的OPT（w-1）也仅是表示背包体积大小为W-1时的“正确解”而已
为什么用OPT？因为这类问题问的一般问都是“最大价值”，“最多”， “最优”的那
个解
仅此而已