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