新手第一次写学习笔记，如果有错，希望有大佬提醒。
本文是手写的，除部分地方外（文中已说明）未用AI润色。
语文不太好，有描述不当处恳请提醒
正文
一：动态规划是什么？它有什么特点？
1.动态规划是什么？
AI对于动态规划是什么这个问题给出的回答是：动态规划是把一个大问题拆成若干子问题，把子问题的答案存起来，避免重复计算，用子问题的结果推出大问题的答案。
而我认为：动态规划实质上是寻找递推规律的算法，后一个子问题的解可以由前面子问题的解推导而来。
2.动态规划有什么特点？
AI对于动态规划有什么特点这个问题给出的回答是：动态规划利用重叠子问题、最优子结构、无后效性，保存子问题的解，递推求出全局最优。
而我认为：他的特点是后一个是由前一个推导出来的，并且后一个如果可以由不同的前一个推导而来，则选择最优答案。
二：动态规划可以用在什么题目上？
AI对此给出的回答是：
1最优子结构：大问题的最优解，由若干子问题的最优解组成
2重叠子问题：拆分后的子问题会重复出现，适合缓存结果
3无后效性 ——当前状态的结果，只由之前的状态决定，和未来状态无关
以上三点便是分辨是否使用动态规划的方法。
三：如何用动态规划解题？
1 首先我们要明白：动态规划的核心是状态转移方程（划重点），我们通过它来描述不同子问题之间的推导关系。
所以，我们解题的第一件事就是：定义动态规划数组（用于状态转移方程），而有的动态规划题目是一维，有的是二维，因此，定义的维度视题目情况而定。
2 其次，便是最主要的状态转移方程的推导（这点我不是很清楚，因此如果有错，恳请指出），一般来说，每个题目的状态转移方程是不一样的，但本质上还是找题目的核心规律，我自己有一些建议，可以看一下：
①明确状态含义，先写清楚：dp[...]dp[...]dp[...]代表什么。
一般来说dp[i]dp[i]dp[i]表示前iii个物品 / 走到第iii位置时，能得到的最优值 / 方案数量。
②思考当前状态可以从哪些前置状态过来
即要得到dp[i]dp[i]dp[i]，前面有哪几种情况可以转移到它？把所有可能的选择枚举出来。
③根据题目要求写状态转移方程
④初始化边界条件
四：实战演练（大佬有好的题推荐吗？整理的真的很辛苦）
T1石板问题
石板问题题目
作为动态规划的入门题目，我就说一下思路：
设 dp[i]dp[i]dp[i]：到达第 i 块石板的方案数
想要到达第 i 块石板：
1. 从i−1i-1i−1石板，跨 1 块过来；
2. 从i−2i-2i−2石板，跨 2 块过来。
递推式：dp[i]=dp[i−1]+dp[i−2]dp[i]=dp[i-1]+dp[i-2]dp[i]=dp[i−1]+dp[i−2]
初始条件：dp[1]=1dp[1]=1dp[1]=1 dp[2]=1dp[2]=1dp[2]=1
> 本质变形斐波那契数列。
代码：
T2石板问题（进阶版）
石板问题（进阶版）题目
此题为上一题的进阶版，思路一样
设 dp[i]dp[i]dp[i]：到达第 i 块石板的方案数
想要到达第 i 块石板：
1. 从i−1i-1i−1石板，跨 1 块过来；
2. 从i−2i-2i−2石板，跨 2 块过来。
3. 从i−3i-3i−3石板，跨 3 块过来。
* 递推式：dp[i]=dp[i−1]+dp[i−2]+dp[i−3]dp[i]=dp[i-1]+dp[i-2]+dp[i-3]dp[i]=dp[i−1]+dp[i−2]+dp[i−3]
* 初始条件：dp[1]=1dp[1]=1dp[1]=1 dp[2]=1dp[2]=1dp[2]=1 dp[3]=2dp[3]=2dp[3]=2
代码：
T3石板问题（通用版）
石板问题（通用版）题目
此题为石板问题通用版，思路一样
设 dp[i]dp[i]dp[i]：到达第 i 块石板的方案数
想要到达第 i 块石板：
上一步一定是从第 i−1,i−2,…,i−ki-1,i-2,\dots,i-ki−1,i−2,…,i−k 块石板跳过来的（不能小于第 1 块石板）。
递推式：dp[i]=∑j=max(1,i−k)i−1dp[j]dp[i]=\sum_{j=max(1,i-k)}^{i-1} dp[j]dp[i]=∑j=max(1,i−k)i−1 dp[j]
初始条件：dp[1]=1dp[1]=1dp[1]=1
代码：
T4最小花费爬楼梯
最小花费爬楼梯题目
未完工
