这个五步法我是看这个文档的，人家写的比我好，大家可以看一看
五步法
推荐蓝桥杯动态规划真题
跳跃
数字三角形
1.确定dp数组（dp table）以及下标的含义
2.确定递推公式
3.dp数组如何初始化
4.确定遍历顺序
5.举例推导dp数组
一，斐波那契数列
1.确定dp数组以及下标含义
dp[i]表示第i个斐波那契数(在做题的时候一定是牢记这一步所表示下标的含义，后面的题大家会越来越体会到其重要性)
2.确定递推公式
dp[i]=dp[i-1]+dp[i-2]，这道题之所以简单就简单在第二步，因为这道题本身已经给出来递推公式，那就是dp[i]=dp[i-1]+dp[i-2],
3.dp数组如何初始化
很显然因为i是由i-1和i-2推出的，所以要初始化dp[1]=1,dp[2]=1
4.确定遍历顺序
从3开始从前到后
5.举例推导dp数组
（这一步主要是用来验证推导的dp数组是否正确）这道题比较简单就不在考虑
现在考虑完这五步，再去写代码就会很顺
二，杨辉三角
1.确定dp数组以及下标含义（意义很大）
dp[i][j]表示的是第i行第j列的杨辉三角
2.确定递推数组（题也包含了这一步）
dp[i][j]=dp[i-1][j]+d[i-1][j-1];
3.dp数组的初始化
i j 是由i-1，j-1
dp[1][1]=1(逻辑不对)
正确：
dp[i][1]=1
dp[i][i]=1
4.确定遍历顺序
从第三行第二列，从左到右，从上到下，但是不包括每一行的最后一列、
5.
略
三，01背包
1.确定dp数组以及下标含义
分析一下就会想到
dp[i][j]表示从0~i的物品装入容量为j的背包的最大价值
2.确定递推公式
再回顾一下dp[i][j]的含义：从下标为[0-i]的物品里任意取，放进容量为j的背包，价值总和最大是多少。
分两种情况，
不装物品i
那么此时的dp[i][j]的最大价值就是dp[i-1][j]，因为放不进i，所以最大加值就是以0~i-1的物品放入容量为j的背包的最大价值
dp[i][j]=dp[i-1][j];
装物品i
dp[i][j] = dp[i - 1][j - weight[i]] + value[i]
看下标含义来解读一下，意思就是以0~i-1的物品放入j-weight[i]的背包的最大价值加上i物品的价值。
这样想是不是就比较清晰了，这就是为什么我一直强调要牢记下标所表示的含义
所以递推公式就是dp[i][j]=Math.max(dp[i-1][j],dp[i - 1][j - weight[i]] + value[i])
3.dp数组如何初始化
因为i是由i-1推出的
所以要初始化dp[0][j]
当weight[0]<j时dp[0][j]=0否则dp[0][j]=15
4.确定遍历顺序
从（1,0）开始从左到右从上到下
5.举例推导dp数组
看图推导一下对不对
网友评论