动态规划问题的小秘籍

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

找状态转移方程的秘决： 找当前状态从哪里来的(上一个状态)。

4、注意事项

动态规划编程实现时用的是表格法，所以要注意赋初始值（递推的起点）。