云浮新兴县做网站,网站空间备案 昆明,怎么做自己的淘客网站,游戏网站app1049.最后一块石头的重量II
思路
本题其实就是尽量让石头分成重量相同的两堆#xff0c;相撞之后剩下的石头最小#xff0c;这样就化解成01背包问题了。
感觉和昨天讲解的416. 分割等和子集 (opens new window)非常像了。
本题物品的重量为 stones[i]#xff0c;物品的价…1049.最后一块石头的重量II
思路
本题其实就是尽量让石头分成重量相同的两堆相撞之后剩下的石头最小这样就化解成01背包问题了。
感觉和昨天讲解的416. 分割等和子集 (opens new window)非常像了。
本题物品的重量为 stones[i]物品的价值也为 stones[i]。
对应着01背包里的物品重量 weight[i]和 物品价值 value[i]。
接下来进行动规五步曲
确定dp数组以及下标的含义
dp[j]表示容量这里说容量更形象其实就是重量为j的背包最多可以背最大重量为dp[j]。
可以回忆一下01背包中dp[j]的含义容量为j的背包最多可以装的价值为 dp[j]。
相对于 01背包本题中石头的重量是 stones[i]石头的价值也是 stones[i] 可以 “最多可以装的价值为 dp[j]” “最多可以背的重量为dp[j]”
确定递推公式
01背包的递推公式为dp[j] max(dp[j], dp[j - weight[i]] value[i]);
本题则是dp[j] max(dp[j], dp[j - stones[i]] stones[i]);
一些同学可能看到这dp[j - stones[i]] stones[i]中 又有- stones[i] 又有stones[i]看着有点晕乎。
大家可以再去看 dp[j]的含义。
dp数组如何初始化
既然 dp[j]中的j表示容量那么最大容量重量是多少呢就是所有石头的重量和。
因为提示中给出1 stones.length 301 stones[i] 1000所以最大重量就是30 * 1000
而我们要求的target其实只是最大重量的一半所以dp数组开到15000大小就可以了。
当然也可以把石头遍历一遍计算出石头总重量 然后除2得到dp数组的大小。
我这里就直接用15000了。
接下来就是如何初始化dp[j]呢因为重量都不会是负数所以dp[j]都初始化为0就可以了这样在递归公式dp[j] max(dp[j], dp[j - stones[i]] stones[i]);中 dp[j]才不会初始值所覆盖。
代码为
int[] dp new int[target1];
确定遍历顺序
在动态规划关于01背包问题你该了解这些滚动数组 (opens new window)中就已经说明如果使用一维dp数组物品遍历的for循环放在外层遍历背包的for循环放在内层且内层for循环倒序遍历
代码如下
for (int i 0; i stones.size(); i) { // 遍历物品for (int j target; j stones[i]; j--) { // 遍历背包dp[j] max(dp[j], dp[j - stones[i]] stones[i]);}
}
举例推导dp数组
举例输入[2,4,1,1]此时target (2 4 1 1)/2 4 dp数组状态图如下 最后dp[target]里是容量为target的背包所能背的最大重量。
那么分成两堆石头一堆石头的总重量是dp[target]另一堆就是sum - dp[target]。
在计算target的时候target sum / 2 因为是向下取整所以sum - dp[target] 一定是大于等于dp[target]的。
那么相撞之后剩下的最小石头重量就是 (sum - dp[target]) - dp[target]。
代码如下
class Solution {public int lastStoneWeightII(int[] stones) {//确定dp数组及其下标含义//dp数组将石头堆分成两堆使两堆的int sum 0;for (int i 0; i stones.length; i) {sum stones[i];}int target sum / 2;int[] dp new int[target1];for (int i 0; i stones.length; i) {for (int j target; j stones[i]; j--) {dp[j] Math.max(dp[j], dp[j - stones[i]] stones[i]);}}return sum - 2*dp[target];}
} 494.目标和
思路
这道题目咋眼一看和动态规划背包啥的也没啥关系。
本题要如何使表达式结果为target
既然为target那么就一定有 left组合 - right组合 target。
left right sum而sum是固定的。right sum - left
公式来了 left - (sum - left) target 推导出 left (target sum)/2 。
target是固定的sum是固定的left就可以求出来。
此时问题就是在集合nums中找出和为left的组合
动态规划
如何转化为01背包问题呢。
假设加法的总和为x那么减法对应的总和就是sum - x。
所以我们要求的是 x - (sum - x) target
x (target sum) / 2
此时问题就转化为装满容量为x的背包有几种方法。
这里的x就是bagSize也就是我们后面要求的背包容量。
大家看到(target sum) / 2 应该担心计算的过程中向下取整有没有影响。
这么担心就对了例如sum 是5S是2的话其实就是无解的所以
C代码中输入的S 就是题目描述的 target
if ((S sum) % 2 1) return 0; // 此时没有方案同时如果 S的绝对值已经大于sum那么也是没有方案的。
C代码中输入的S 就是题目描述的 target
if (abs(S) sum) return 0; // 此时没有方案再回归到01背包问题为什么是01背包呢
因为每个物品题目中的1只用一次
这次和之前遇到的背包问题不一样了之前都是求容量为j的背包最多能装多少。
本题则是装满有几种方法。其实这就是一个组合问题了。
确定dp数组以及下标的含义
dp[j] 表示填满j包括j这么大容积的包有dp[j]种方法
其实也可以使用二维dp数组来求解本题dp[i][j]使用 下标为[0, i]的nums[i]能够凑满j包括j这么大容量的包有dp[i][j]种方法。
下面都是统一使用一维数组进行讲解 二维降为一维滚动数组其实就是上一层拷贝下来这个我在动态规划关于01背包问题你该了解这些滚动数组 (opens new window)也有介绍。
确定递推公式
有哪些来源可以推出dp[j]呢
只要搞到nums[i]凑成dp[j]就有dp[j - nums[i]] 种方法。
例如dp[j]j 为5
已经有一个1nums[i] 的话有 dp[4]种方法 凑成 容量为5的背包。已经有一个2nums[i] 的话有 dp[3]种方法 凑成 容量为5的背包。已经有一个3nums[i] 的话有 dp[2]中方法 凑成 容量为5的背包已经有一个4nums[i] 的话有 dp[1]中方法 凑成 容量为5的背包已经有一个5 nums[i]的话有 dp[0]中方法 凑成 容量为5的背包
那么凑整dp[5]有多少方法呢也就是把 所有的 dp[j - nums[i]] 累加起来。
所以求组合类问题的公式都是类似这种
dp[j] dp[j - nums[i]]这个公式在后面在讲解背包解决排列组合问题的时候还会用到
dp数组如何初始化
从递推公式可以看出在初始化的时候dp[0] 一定要初始化为1因为dp[0]是在公式中一切递推结果的起源如果dp[0]是0的话递推结果将都是0。
这里有录友可能认为从dp数组定义来说 dp[0] 应该是0也有录友认为dp[0]应该是1。
其实不要硬去解释它的含义咱就把 dp[0]的情况带入本题看看应该等于多少。
如果数组[0] target 0那么 bagSize (target sum) / 2 0。 dp[0]也应该是1 也就是说给数组里的元素 0 前面无论放加法还是减法都是 1 种方法。
所以本题我们应该初始化 dp[0] 为 1。
可能有同学想了那 如果是 数组[0,0,0,0,0] target 0 呢。
其实 此时最终的dp[0] 32也就是这五个零 子集的所有组合情况但此dp[0]非彼dp[0]dp[0]能算出32其基础是因为dp[0] 1 累加起来的。
dp[j]其他下标对应的数值也应该初始化为0从递推公式也可以看出dp[j]要保证是0的初始值才能正确的由dp[j - nums[i]]推导出来。
确定遍历顺序
在动态规划关于01背包问题你该了解这些滚动数组 (opens new window)中我们讲过对于01背包问题一维dp的遍历nums放在外循环target在内循环且内循环倒序。
举例推导dp数组
输入nums: [1, 1, 1, 1, 1], S: 3
bagSize (S sum) / 2 (3 5) / 2 4
dp数组状态变化如下 代码如下
class Solution {public int findTargetSumWays(int[] nums, int target) {int sum 0;for (int i 0; i nums.length; i) sum nums[i];//如果target过大 sum将无法满足if ( target 0 sum -target) return 0;if ((target sum) % 2 ! 0) return 0;int size (target sum) / 2;if(size 0) size -size;int[] dp new int[size 1];dp[0] 1;for (int i 0; i nums.length; i) {for (int j size; j nums[i]; j--) {dp[j] dp[j - nums[i]];}}return dp[size];}
} 474.一和零
思路
这道题目还是比较难的也有点像程序员自己给自己出个脑筋急转弯程序员何苦为难程序员呢。
本题并不是多重背包再来看一下这个图捋清几种背包的关系 多重背包是每个物品数量不同的情况。
本题中strs 数组里的元素就是物品每个物品都是一个
而m 和 n相当于是一个背包两个维度的背包。
理解成多重背包的主要是把m和n混淆为物品了感觉这是不同数量的物品所以以为是多重背包。
但本题其实是01背包问题
只不过这个背包有两个维度一个是m 一个是n而不同长度的字符串就是不同大小的待装物品。
开始动规五部曲
确定dp数组dp table以及下标的含义
dp[i][j]最多有i个0和j个1的strs的最大子集的大小为dp[i][j]。
确定递推公式
dp[i][j] 可以由前一个strs里的字符串推导出来strs里的字符串有zeroNum个0oneNum个1。
dp[i][j] 就可以是 dp[i - zeroNum][j - oneNum] 1。
然后我们在遍历的过程中取dp[i][j]的最大值。
所以递推公式dp[i][j] max(dp[i][j], dp[i - zeroNum][j - oneNum] 1);
此时大家可以回想一下01背包的递推公式dp[j] max(dp[j], dp[j - weight[i]] value[i]);
对比一下就会发现字符串的zeroNum和oneNum相当于物品的重量weight[i]字符串本身的个数相当于物品的价值value[i]。
这就是一个典型的01背包 只不过物品的重量有了两个维度而已。
dp数组如何初始化
在动态规划关于01背包问题你该了解这些滚动数组 (opens new window)中已经讲解了01背包的dp数组初始化为0就可以。
因为物品价值不会是负数初始为0保证递推的时候dp[i][j]不会被初始值覆盖。
确定遍历顺序
在动态规划关于01背包问题你该了解这些滚动数组 (opens new window)中我们讲到了01背包为什么一定是外层for循环遍历物品内层for循环遍历背包容量且从后向前遍历
那么本题也是物品就是strs里的字符串背包容量就是题目描述中的m和n。
代码如下
for (String str : strs) {// 遍历物品//0 的个数int x 0;//1 的个数int y 0;for (char c : str.toCharArray()) {if (c0){x;}else if (c1){y;}}for (int i m; i x; i--) {// 遍历背包容量且从后向前遍历for (int j n; j y; j--) {dp[i][j] Math.max(dp[i][j],dp[i-x][j-y]1);}}
}
那个遍历背包容量的两层for循环先后循序有没有什么讲究
没讲究都是物品重量的一个维度先遍历哪个都行
举例推导dp数组
以输入[10,0001,111001,1,0]m 3n 3为例
最后dp数组的状态如下所示 代码如下
class Solution {public int findMaxForm(String[] strs, int m, int n) {int[][] dp new int[m1][n1];for (String str : strs) {// 遍历物品//0 的个数int x 0;//1 的个数int y 0;for (char c : str.toCharArray()) {if (c0){x;}else if (c1){y;}}for (int i m; i x; i--) {// 遍历背包容量且从后向前遍历for (int j n; j y; j--) {dp[i][j] Math.max(dp[i][j],dp[i-x][j-y]1);}}}return dp[m][n];}
} 动态规划真想不出来感觉是强行将题目解释成01背包问题的
