AKSZ-动态规划
2024-06-16 17:55:09
发布于:广东
怎么想dp(以斐波那契为例)
1.划分阶段->斐波那契数列的每一项作为一个阶段
2.确定状态->第i
项的值用a[i]
来表示(结尾法)
3.确定决策+想状态转移方程式->每一项的值都是前两项的和:a[i]=a[i-1]+a[i-2]
何时用dp
1.最优化原理(最优子结构):
如果最优解所包含的子问题的解也是最优的,就称该问题具有最优子结构,即满足最优化原理。
2.无后效性:
即某阶段一旦确定,就不受这个状态以后决策的影响。也就是说,某状态以后的进程保活影响以前的状态,只与当前状态有关。
3.子问题重叠
即子问题之间是不独立的,一个子问题在下一阶段决策中可能被多次使用到。
注:非dp适用必要条件,但如果没有此性质,dp就不会比其他算法更有优势。
这里空空如也
有帮助,赞一个