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