z****j
发帖数: 111 | 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***x
发帖数: 45 | 2 最有子结构是个概念
你把问题divide成很多小的，分别求最优，然后合并起来
但问题是，合并起来的不一定是最优的
你要证明合并起来的也是最优的=> optimal substructure |
V*********r
发帖数: 666 | 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******u
发帖数: 550 | 4 如果你想求得最优解的话是必须的了，如果只是想sub-optimal的话可以track sub-
problem的optimality gap in a tolerated range. |
l******n
发帖数: 1250 | 5 楼主应该不是要解最优化问题,而是在做coding题 |
z****j
发帖数: 111 | 6 我明白你说的意思，但像fibonacci那个dp的解法一样，overlapping substructure很
明显，但是却看不出有什么Optimal substructure？但是为什么还划在了DP的范畴，换
句话就是optimal substructure是DP的必要条件么？
【在 g***x 的大作中提到】
: 最有子结构是个概念
: 你把问题divide成很多小的，分别求最优，然后合并起来
: 但问题是，合并起来的不一定是最优的
: 你要证明合并起来的也是最优的=> optimal substructure
|
z****j
发帖数: 111 | 7 我只是好奇optimal substructure是DP的必要条件么？换句话说能够应用DP的问题一定
要有optimal substructure么？
【在 l******n 的大作中提到】
: 楼主应该不是要解最优化问题,而是在做coding题
|
z****j
发帖数: 111 | 8 可能是我理解有点问题... 不过像fib（n） = fib（n-1） + fib（n-2）这样的递归式
它的optimal点体现在哪里呢？这个也可以算是optimal substructure吗
【在 V*********r 的大作中提到】
: 能写出Bellman递推等式的就有optimal substructure，fib那个递归式就是
: 规避重复计算靠的是overlapping subproblems
:
: substructure
|
J*****a
发帖数: 4262 | 9 opt的意思不是“最优解法”，optimal不是你想的算法复杂度最优的“优”
而是正确解的意思
比如背包问题，背包体积为W，那么W能放下的最大价值为OPT（W）
那这个OPT（W）表示的其实是背包体积为W时的“正确解”
同理，你找出了OPT（W）和OPT（W-1）、OPT（W-2）.。。的关系之后就可以解这题了
这里的OPT（w-1）也仅是表示背包体积大小为W-1时的“正确解”而已
为什么用OPT？因为这类问题问的一般问都是“最大价值”，“最多”， “最优”的那
个解
仅此而已 |
