动态规划（一）什么是动态规划？

1.动态规划是什么？

动态规划：动态规划常见基础题目之一。

官方的解释是：

????????动态规划（Dynamic Programming，DP）是运筹学的一个分支，是求解决策过程最优化的过程。

?我的理解：

? ? ? ? 动态规划总是体现在当前状态由前面的状态推导而来，前面的状态由更前面的状态推导。最开始的状态由定义给出，按照递推公式一步一步推导到当前状态。

? ? ? ? 动态规划=给定起始+按照一定规律逐步推导到下一位置状态。

2.动态规划一般用于解决什么问题？

常见题型：

• 斐波那契数列、爬楼梯问题
• 完全背包、背包问题
• 打家劫舍（树形DP）
• 股票问题
• 子序列问题

拔尖题型：

• 区间DP 、概率DP

3.动态规划解题一般有哪些步骤？

1. 明确dp数组及下标的含义。
2. 确定递推公式，但是递推公式只是动态规划的一部分，而非全部
3. dp数组初始化
4. 确定遍历顺序：从前往后？从后往前？
5. 打印dp数组, 用于debug验证等。

代码实现的步骤与思路的步骤是有区别的：

• ? ? ? ? 定义dp数组
• ? ? ? ? 初始化数组
• ? ? ? ? 遍历
• ? ? ? ? 递推公式

4.总结

题型识别： 给定初始状态，后面的状态总是由前面的状态决定。

解题步骤：动态规划五部曲：dp[i]含义、递推公式、初始化、遍历顺序、打印debug

掌握方式：多题练习