动态规划从入坟走向入坑

目录

1.动态规划的含义
2.动态规划的解题步骤(动规五部曲)
3.动态规划的题型
 4.相关思路
1.动规底子(由于我看的博主讲的动规很简朴,以是这里就不讲了)
2.背包问题
1.二维dp数组01背包
1.dp[j] 表示从下标为[0-i]的物品里恣意取，放进容量为j的背包，代价总和最大是多少。
2.确定递推公式   最大值dp[j]
3.dp数组的初始化(这里就不给图了)
4. 确定遍历序次

 5.举例推导dp数组打印dp数组看是否与标题答案同等
2.一维dp数组01背包（滚动数组）
1.dp 表示容量为j的背包，代价总和最大是多少。
2.确定递推公式   最大值dp[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 表示背包各个物品的重量
value  表示各个物品的代价
1.二维dp数组01背包

动规五部曲分析一波。
两个方向遍历 物品 和 背包涵量

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

 二维嘛,一定有i和j变量
  ( 传统i 来表示物品、j表示背包涵量。)
（假如想用j 表示物品，i 表示背包涵量 行不可？ 都可以的，个人习惯而已）

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

要时刻记着这个dp数组的含义，下面的一些步骤都围绕这dp数组的含义举行的
也就是两种状态去或者不取,容量j背包背包背的最大代价
 假如还是不理解的话,那我举个搬家例子吧
那是一个晴朗的清晨,那天我必要搬东西回家,但是我必要坐高铁,东西带不了那么多,于是乎我只带了很多贵重的东西回家,我必要想的是带更多的有代价的东西,使其达到最大值
当然不必说寄快递,因为本身,它的代价就并不高,嘿嘿嘿嘿嘿嘿嘿嘿
这里应该解释的非常清晰了
2.确定递推公式   最大值dp[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] + value

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

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

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

做如此高质量的文章,太费时间了,感觉我背面的不会如此久了,今天下战书,就学习到了这,也大概是我码字的速度比较慢吧
起首从dp[j]的定义出发，假如背包涵量j为0的话，即dp[0]，无论是选取哪些物品，背包代价总和一定为0。


在看其他环境。
状态转移方程 dp[j] = max(dp[i - 1][j], dp[i - 1][j - weight] + value); 可以看出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[0] 都已经初始化了，那么其他下标应该初始化多少呢？


其实从递归公式： dp[j] = max(dp[i - 1][j], dp[i - 1][j - weight] + value); 可以看出dp[j] 是由左上方数值推导出来了，那么 其他下标初始为什么数值都可以，因为都会被覆盖。
初始-1，初始-2，初始100，都可以！
但只不外一开始就统一把dp数组统一初始为0，更方便一些。


4. 确定遍历序次

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

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

复制代码

 先遍历背包，再遍历物品

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

复制代码

 5.举例推导dp数组打印dp数组看是否与标题答案同等

来看一下对应的dp数组的数值，如图：(左边是物品0物品1物品2)
引用哔哩哔哩代码随想录与上文同等
                                 背包重量       1                     2                  3                  4                     5

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

这里我引用了哔哩哔哩博主代码随想录的,我觉得讲的很好!带你学透01背包问题（滚动数组篇） | 从此对背包问题不再渺茫！_哔哩哔哩_bilibili
1.dp 表示容量为j的背包，代价总和最大是多少。

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

接下来还是用如下这个例子来举行讲授一维dp数组01背包
背包最大重量为4。
物品为：

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

对于背包问题其实状态都是可以压缩的。
   在使用二维数组的时候，递推公式：dp[j] = max(dp[i - 1][j], dp[i - 1][j - weight] + value);
  其实可以发现是dp[j]递推公式是由当前层和上一层复制dp[i - 1][j]还有放了i的最大代价dp[i - 1][j - weight] + value)
  因为是引用了上层数据,以是标题称为滚动.
这就是滚动数组的由来，必要满足的条件是上一层可以重复利用，直接拷贝到当前层。
读到这里估计各人都忘了 dp[j]里的i和j表达的是什么了，i是物品，j是背包涵量。
dp[j] 表示从下标为[0-i]的物品里恣意取，放进容量为j的背包，代价总和最大是多少。
   一维dp数组，其实就上一层 dp[i-1] 这一层 拷贝的 dp来。
  以是在 上面递推公式的底子上，去掉i这个维度就好。
  递推公式为：dp[j] = max(dp[j], dp[j - weight] + value);
  
3.一维dp数组如何初始化

关于初始化，一定要和dp数组的定义符合，否则到递推公式的时候就会越来越乱。
dp[j]表示：容量为j的背包，所背的物品代价可以最大为dp[j]，那么dp[0]就应该是0，因为背包涵量为0所背的物品的最大代价就是0。

那么dp数组除了下标0的位置，初始为0，其他下标应该初始化多少呢？
看一下递归公式：dp[j] = max(dp[j], dp[j - weight] + value);
dp数组在推导的时候一定是取代价最大的数，标题一般是正整数,以是这里我保举直接初始化为0.

如许才气让dp数组在递归公式的过程中取的最大的代价，而不是被初始值覆盖了。
那么我假设物品代价都是大于0的，以是dp数组初始化的时候，都初始为0就可以了。


4. 确定遍历序次

代码如下：

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

复制代码

这里各人发现和二维dp的写法中，遍历背包的序次是不一样的！但是其实还是要两层for循环
二维dp遍历的时候，背包涵量是从小到大，而一维dp遍历的时候，背包是从大到小。
为什么呢？
我的理解是从后往前遍历,其实就是保证了背包dp[]的最大代价
因为二维省去了一维的i以是我们不知道是否前面带了物品i,大概会导致背面重复带物品i,以是我们从背面开始,从前面开始的话,就可以出现物美价廉的东西本身买多了,只能买一次,效果带了两次,没有考虑到前面的状态,已经买过了.

5.举例推导dp数组

引用哔哩哔哩代码随想录与上文同等

文献引用

代码随想录..代码随想录非常保举,很值得学习的博主

代码还没有敲,就到了吃饭的点了,兄弟们,多点赞支持一下,没有赞就没有动力,谢谢个位大佬!! 
(背面修缮了一下,又肝了一个小时)
还望大佬一键三连 (如有误,请大佬指出,谢谢!!)

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。