动态规划问题的小秘籍
1、动态规划的基本思想:将待求解问题分解成若干个子问题,先求解子问题,然后从这些子问题的解得到原问题的解。
2、适用动态规划的条件:
最优子结构
子问题重叠
无后效性
3、分析动态规划必须分析的三个基本要素:
阶段、状态、决策
比如:“黑熊过河”
阶段:石墩
状态:dp[i]:记录到达第i个石墩剩余能量的最大值。
决策:dp[i]=max{ dp[i-1], dp[i-2]}-q+a[i];
且 max{ dp[i-1], dp[i-2]}-q>=0