动态规划解题方法

动态规划通常用来求某个问题的最优解，将一个问题分解成若干个子问题，先求解子问题，然后从子问题的解中慢慢推导得到原问题的解。

动态规划算是做算法题时一种比较难的算法，记录一下从代码随想录的动态规划解题方法论中学到的动规做题五部曲。

动态规划题目类型

• 动规基础(入门：斐波那契数列、爬楼梯等)
• 背包问题
• 打家劫舍
• 股票问题
• 子序列问题
• 区间dp、概率dp(算法拔尖题)

动规五部曲

1.确定dp数组以及下标的含义

需要明白做题所定义的dp数组到底表示什么含义，以及当dp数组为一维数组时，dp[i]表示什么；当dp数组为二维数组时，dp[i][j]中的i和j分别表示什么含义。

2.递推公式(状态转移方程式)

想出递推公式才能够顺利解题。

3.dp数组的初始化

想明白问题最初的子问题的解是什么，初始化的值对了后面的推导才是正确的。

4.dp数组的遍历顺序

考虑清楚dp数组的遍历顺序，比如有正向dp和反向dp，反向dp就会从dp数组的末尾往前推导。再比如背包问题：是先遍历背包后遍历物品还是先遍历物品再遍历背包。

5.打印dp数组

当结果不对时，往往因为动规的代码比较简单而很难推断是哪里出了问题，那么将dp数组中的每一个值打印出来就能方便调试。