DP动态规划模板
2025-04-06 08:21:36
发布于：上海
食用说明:主播第一次上完DP写的小笔记,应该比较亲民,但是主播在上课之前是有C++基础的
适用群体:学过输入输出,判断,for循环的人类
DP(动态规划)的用处:当n>20,也就是不能用爆搜(DFS)解决时,可以尝试用DP来解决.
一.DP模板
1.状态表示
一般就是答案要求什么，就表示什么
比如：斐波那契数列：
a[i]就是第i个斐波那契数列得知
2.答案
根据状态表示，决定答案
3.状态转移方程
重要在转移：从先前求出的数值转移，决定要求的数值
4.遍历方向
比如数字金字塔：就可以从上到下或者从下到上
5.初始化
状态转移时数字可能会越界，所以就需要初始化
当这5个条件全部考虑到位,你就能AC了(窝老史说的)
接下来列举一些有关它们的题目,帮助理解:
二.例题
钞票问题:
1.状态表示:
上文提到过,答案要求什么就表示什么:这个表示指的是你要列一个怎样的数组.
比如钞票问题要求凑够n元需要的最少纸币.
那么可以做出一个数组:
dp[1000];
dp[i]表示凑够n元需要的最少纸币.
2.答案:
既然dp[i]表示的是凑够n元需要的最少数量的纸币,那么答案就是dp[n]
3.状态转移方程:
上文提到过"转移"就是从先前求出的数值转移，决定要求的数值.
那么在钞票问题中如何利用先前求出过的数值转移呢?
我们知道有1,5,11元的纸币.
那么在我们求dp[i]的时候,我们可以从3个之前求出过的数值来"转移",它们就是:
dp[i-1] dp[i-5] dp[i-11]
只要将这三个数值中的最小值+1就是dp[i]的数值
*因为分别由1,5,11的三张钞票;最小值是因为要求最少数量的纸币.
此时不需要考虑遍历方向
5.初始化:
只有一个点需要注意:
上文提到的 i-1 , i-5 和 i-11 是否会是负数
解决方案:判断一下就好了
但这个好像不算初始化吧
核心代码:
for(int i=1;i<=n;i++){
if(i>=11){
a[i]=min(a[max(0,i-1)],min(a[max(0,i-5)],a[max(0,i-11)]))+1;
} else if(i>=5){
a[i]=min(a[max(0,i-1)],a[max(0,i-5)])+1;
}else a[i]=a[max(0,i-1)]+1;
}
数字金字塔:
1.状态表示:
虽然它是一个金字塔,但可以直接看成数组:
题目想要路径经过数字最大和(也就是从第一行到最后一行经过的数字和的最大值)
那么我们可以用一个二维数组:
dp[105][105];
dp[i][j]表示从第1行第1列的数到第i行第j列的数的最大值(听起来可能怪怪的,但希望大家尝试去理解)
2.答案
最大值一定在最后一行里,所以直接利用for循环取出最后一行的最大值.
for(int i=1;i<=n;i++){
answer=max(answer,dp[n][i]);
}
3.状态转移方程:
我们知道,这个橙色的点,可以到达自己左下方的点和自己右下方的点(也就是那两个绿的):
所以,同样的每一个绿点会有自己左上方的点和右上方的点,它可以选择左上方的累计值,也可以选择右上方的累计值,我们当然选更大的,也就是:
dp[i][j]=max(dp[i-1][j-1],dp[i-1][j+1);
别忘了,(i,j)这个位置本身也是有值的,所以就是:
dp[i][j]=max(dp[i-1][j-1],dp[i-1][j+1)+a[i][j];
4.遍历方向:
这里有两个方向:
1.从上至下
2.从下至上
由于主播太菜,所以只学习了从上至下(这样比较适合新人理解),所以这里我们选择从上至下
(有感兴趣的小伙伴也可以自己研究一下从下至上哦)
5.初始化
从上至下不需要初始化.
核心代码:
for(int i=1;i<=n;i++){
for(int j=1;j<=i;j++){
dp[i][j]=max(dp[i-1][j],dp[i-1][j-1])+a[i][j];
}
}
类似题目:T18992.不同的路径
传球游戏:
有帮助，赞一个