动态规划从入坟走向入坑

1.动态规划的含义

2.动态规划的解题步骤(动规五部曲)

3.动态规划的题型

4.相关思路

1.动规基础(由于我看的博主讲的动规很简单,所以这里就不讲了)

2.背包问题

1.二维dp数组01背包

1.dp[i][j] 表示从下标为[0-i]的物品里任意取，放进容量为j的背包，价值总和最大是多少。

2.确定递推公式最大值dp[i][j]

3.dp数组的初始化(这里就不给图了)

4. 确定遍历顺序

5.举例推导dp数组打印dp数组看是否与题目答案一致

2.一维dp数组01背包（滚动数组）

1.dp[i] 表示容量为j的背包，价值总和最大是多少。

2.确定递推公式最大值dp[i][j]

3.一维dp数组如何初始化

4. 确定遍历顺序

5.举例推导dp数组

文献引用

1.动态规划的含义

动态规划，英文：Dynamic Programming，简称DP(很多题解代码都是用的dp)(所以这里解释一下dp含义)，如果某一问题有很多重叠子问题，使用动态规划是最有效的。

所以动态规划中每一个状态一定是由上一个状态推导出来的，这一点就区分于贪心，贪心没有状态推导，而是从局部直接选最优的.

2.动态规划的解题步骤(动规五部曲)

1.确定dp数组以及下标的含义

2.确定递推公式

3.确定dp数组的初始化

4.确定遍历顺序

5.举例推导dp数组打印dp数组看是否与题目答案一致

3.动态规划的题型

1.动规基础

2.背包问题

3.打家劫舍

4.股票问题

5.子序列问题

4.相关思路

(今天先讲01背包哦),因为只学到这儿

1.动规基础(由于我看的博主讲的动规很简单,所以这里就不讲了)

2.背包问题

在下面的讲解中，我举一个例子：

背包最大重量为4。

物品为：

	重量	价值
物品0	1	15
物品1	3	20
物品2	4	30

问背包能背的物品最大价值是多少？

以下讲解和图示中出现的数字都是以这个例子为例。

weight[i] 表示背包各个物品的重量

value[i] 表示各个物品的价值

1.二维dp数组01背包

动规五部曲分析一波。

两个方向遍历 物品和背包容量

	i
j		重量	价值
	物品0
	物品1
	物品2

二维嘛,必然有i和j变量

( 传统i 来表示物品、j表示背包容量。)

（如果想用j 表示物品，i 表示背包容量行不行？都可以的，个人习惯而已）

1.dp[i][j] 表示从下标为[0-i]的物品里任意取，放进容量为j的背包，价值总和最大是多少。

要时刻记着这个dp数组的含义，下面的一些步骤都围绕这dp数组的含义进行的

也就是两种状态去或者不取,容量j背包背包背的最大价值

如果还是不理解的话,那我举个搬家例子吧

那是一个晴朗的早晨,那天我需要搬东西回家,但是我需要坐高铁,东西带不了那么多,于是乎我只带了很多贵重的东西回家,我需要想的是带更多的有价值的东西,使其达到最大值

当然不必说寄快递,因为本身,它的价值就并不高,嘿嘿嘿嘿嘿嘿嘿嘿

这里应该解释的非常清楚了

2.确定递推公式最大值dp[i][j]

前面乎3已经确定了含义,这里我们来到递推公式

	重量	价值
物品0	1	15
物品1	3	20
物品2	4	30

这里我们来求两种情况，分别是放物品1 和不放物品1，我们要取最大值（毕竟求的是最大价值）

dp[1][3] = max(dp[0][3], dp[0][1] + 物品1 的价值)

放物品1 dp[i - 1][j]

不放物品1dp[i - 1][j - weight[i]] + value[i]

物品\背包容量	背包容量0	背包容量1	背包容量2	背包容量3	背包容量4
物品0	0	15	15	15	15
物品1	0	15	15	20
物品2	0
	0
	0

再在看其他情况。

状态转移方程 dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - weight[i]] + value[i]); 可以看出i 是由 i-1 推导出来，那么i为0的时候就一定要初始化。

3.dp数组的初始化(这里就不给图了)

做如此高质量的文章,太费时间了,感觉我后面的不会如此久了,今天下午,就学习到了这,也可能是我码字的速度比较慢吧

首先从dp[i][j]的定义出发，如果背包容量j为0的话，即dp[i][0]，无论是选取哪些物品，背包价值总和一定为0。

在看其他情况。

状态转移方程 dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - weight[i]] + value[i]); 可以看出i 是由 i-1 推导出来，那么i为0的时候就一定要初始化。

dp[0][j]，即：i为0，存放编号0的物品的时候，各个容量的背包所能存放的最大价值。

那么很明显当 j < weight[0]的时候，dp[0][j] 应该是 0，因为背包容量比编号0的物品重量还小。

当j >= weight[0]时，dp[0][j] 应该是value[0]，因为背包容量放足够放编号0物品。

dp[0][j] 和 dp[i][0] 都已经初始化了，那么其他下标应该初始化多少呢？

其实从递归公式： dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - weight[i]] + value[i]); 可以看出dp[i][j] 是由左上方数值推导出来了，那么其他下标初始为什么数值都可以，因为都会被覆盖。

初始-1，初始-2，初始100，都可以！

但只不过一开始就统一把dp数组统一初始为0，更方便一些。

4. 确定遍历顺序

这里给出先遍历物品，然后遍历背包重量的代码

// weight数组的大小 就是物品个数
for (int i = 1; i < strlen(weight); i++) { // 遍历物品
    for (int j = 0; j <= strlen(beibao); j++) { // 遍历背包容量
        if (j < weight[i]) dp[i][j] = dp[i - 1][j];
        else dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - weight[i]] + value[i]);

    }
}

先遍历背包，再遍历物品

// weight数组的大小 就是物品个数
for (int j = 0; j <= strlen(beibao); j++) { // 遍历背包容量
    for (int i = 1; i < strlen(weight)); i++) { // 遍历物品
        if (j < weight[i]) dp[i][j] = dp[i - 1][j];
        else dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - weight[i]] + value[i]);
    }
}

5.举例推导dp数组打印dp数组看是否与题目答案一致

来看一下对应的dp数组的数值，如图：(左边是物品0物品1物品2)

引用哔哩哔哩代码随想录与上文一致

背包重量 1 2 3 4 5

2.一维dp数组01背包（滚动数组）

这里我引用了哔哩哔哩博主代码随想录的,我觉得讲的很好!带你学透01背包问题（滚动数组篇） | 从此对背包问题不再迷茫！_哔哩哔哩_bilibili

1.dp[i] 表示容量为j的背包，价值总和最大是多少。

2.确定递推公式最大值dp[i][j]

接下来还是用如下这个例子来进行讲解一维dp数组01背包

背包最大重量为4。

物品为：

	重量	价值
物品0	1	15
物品1	3	20
物品2	4	30

对于背包问题其实状态都是可以压缩的。

在使用二维数组的时候，递推公式：dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - weight[i]] + value[i]);

其实可以发现是dp[i][j]递推公式是由当前层和上一层复制dp[i - 1][j]还有放了i的最大价值dp[i - 1][j - weight[i]] + value[i])

因为是引用了上层数据,所以题目称为滚动.

这就是滚动数组的由来，需要满足的条件是上一层可以重复利用，直接拷贝到当前层。

读到这里估计大家都忘了 dp[i][j]里的i和j表达的是什么了，i是物品，j是背包容量。

dp[i][j] 表示从下标为[0-i]的物品里任意取，放进容量为j的背包，价值总和最大是多少。

一维dp数组，其实就上一层 dp[i-1] 这一层拷贝的 dp[i]来。

所以在上面递推公式的基础上，去掉i这个维度就好。

递推公式为：dp[j] = max(dp[j], dp[j - weight[i]] + value[i]);

3.一维dp数组如何初始化

关于初始化，一定要和dp数组的定义吻合，否则到递推公式的时候就会越来越乱。

dp[j]表示：容量为j的背包，所背的物品价值可以最大为dp[j]，那么dp[0]就应该是0，因为背包容量为0所背的物品的最大价值就是0。

那么dp数组除了下标0的位置，初始为0，其他下标应该初始化多少呢？

看一下递归公式：dp[j] = max(dp[j], dp[j - weight[i]] + value[i]);

dp数组在推导的时候一定是取价值最大的数，题目一般是正整数,所以这里我推荐直接初始化为0.

这样才能让dp数组在递归公式的过程中取的最大的价值，而不是被初始值覆盖了。

那么我假设物品价值都是大于0的，所以dp数组初始化的时候，都初始为0就可以了。

4. 确定遍历顺序

代码如下：

for(int i = 0; i < strlen(weight); i++) { // 遍历物品
    for(int j = strlen(beibao); j >= weight[i]; j--) { // 遍历背包容量
        dp[j] = max(dp[j], dp[j - weight[i]] + value[i]);

    }
}

这里大家发现和二维dp的写法中，遍历背包的顺序是不一样的！但是其实还是要两层for循环

二维dp遍历的时候，背包容量是从小到大，而一维dp遍历的时候，背包是从大到小。

为什么呢？

我的理解是从后往前遍历,其实就是保证了背包dp[]的最大价值

因为二维省去了一维的i所以我们不知道是否前面带了物品i,可能会导致后面重复带物品i,所以我们从后面开始,从前面开始的话,就可以出现物美价廉的东西自己买多了,只能买一次,结果带了两次,没有考虑到前面的状态,已经买过了.