动态规划交流会议总结

这个五步法我是看这个文档的，人家写的比我好，大家可以看一看

五步法

推荐蓝桥杯动态规划真题

跳跃

数字三角形

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数组

看图推导一下对不对