刷题笔记 动态规划-1 动态规划理论基础
一、动态规划题目类型
1.动规基础题目
包括常见的斐波那契数列、爬楼梯
2.背包问题
经典动归，面试常考。包括背包、完全背包和多重背包
3.打家劫舍
力扣上只有三道，但比较经典，尤其是最后一道树形动规
4.股票问题
经典系列问题
5.子序列问题
经典问题，包括子序列、连续子序列、编辑距离问题和回文子序列
6.其他：例如区间动规、概率动规
这些是拔尖的，至少我用不到
二、动态规划五部曲
1.确定dp数组定义以及下标含义
2.递推公式
3.初始化方式
4.遍历顺序
5.举例推导（打印DP数组）
1.为什么先确定递推公式再初始化
因为一些情况是递推公式决定了dp数组要如何初始化！（代码随想录）
但递推公式并不代表一切，初始化顺序很考究
2.TIPS and debug
1.做动规的题目，写代码之前一定要把状态转移在dp数组的上具体情况模拟一遍，心中有数，确定最后推出的是想要的结果。
2.找问题的最好方式就是把dp数组打印出来，看看究竟是不是按照自己思路推导的！
3.debug三问：
- 这道题目我举例推导状态转移公式了么？
- 我打印dp数组的日志了么？
- 打印出来了dp数组和我想的一样么？