代码随想录算法训练营第三十五天 | leetcode：最后一块石头的重量 II,目标和,一和零
0 / 0 / 创建于 11个月前
_zzh 的个人博客
1049. 最后一块石头的重量 II
解题方法
- 思路：尽量让石头分成重量相同的两堆，相撞之后剩下的石头最小。背包容量为sum/2,这里有个小细节，有小数时，需要向下取整，这样sum - dp[target] 一定是大于等于dp[target]的。物品就是石头，石头的价值与重量都是stones[i]。这样就把问题转换成背包问题了。
- 确定dp数组以及下标的含义：dp[j]表示容量（这里说容量更形象，其实就是重量）为j的背包，最多可以背最大重量为dp[j]。
- 确定递推公式：dp[j] = max(dp[j], dp[j - weight[i]] + value[i]);
- 既然 dp[j]中的j表示容量，那么最大容量（重量）是多少呢，就是所有石头的重量和。因为提示中给出1 <= stones.length <= 30，1 <= stones[i] <= 100，所以最大重量就是30 * 100 。而我们要求的target其实只是最大重量的一半，所以dp数组开到1500大小就可以了。值全部初始化为0即可。
- 确定遍历顺序：物品遍历的for循环放在外层，遍历背包的for循环放在内层，且内层for循环倒序遍历！
code
class Solution {
/**
* @param Integer[] $stones
* @return Integer
*/
function lastStoneWeightII($stones) {
$dp = array_fill(0, 1500, 0);
$len = count($stones);
$sum = 0;
//$dp = [];
//求和过程
for($i = 0; $i <= $len-1; $i++){
//$dp[$stones[$i]] = 0;
$sum += $stones[$i];
}
//向下取整
$target = floor($sum/2);
for($i = 0; $i < $len; $i++){
for($j = $target; $j >= $stones[$i]; $j--){
$dp[$j] = max($dp[$j],$dp[$j - $stones[$i]] + $stones[$i]);
}
}
//因为target向下取整sum - dp[target] 一定是大于等于dp[target]的。
$surplus = ($sum - $dp[$target]) - $dp[$target];
return $surplus;
}
}复杂度
时间复杂度
O(m × n) , m是石头总重量（准确的说是总重量的一半），n为石头块数
空间复杂度
O(m)
494. 目标和
解题方法
思路：这题需要先推导数学公式，再由数学公式推到dp数组。
- 数学公式推导：假设：sum(P)为所有需要设为正数的和，sum(N)为所有需要设为负数的和。则得出
- sum(P) - sum(N) = target;
- sum(P) + sum(N) = sum(给定数值的和);
- sum(N) = sum - sum(P);
- 代入sum(N)到第一个式子：sum(P) - (sum - sum(P)) = target;
- 去括号交换左右项可以得：sum(P) + sum(P) = target + sum;
- 最后可得：sum(P) = (target + sum)/2; 这里假设sum(P)不为整数的话，代表题目无解，因为题目指定nums为非负整数数组，而整数没办法组合成小数。
- 由上面数学公式可以得出：计算出需要设为正数和为sum(P)有几种方式，就是最终需要求得的结果。那么就可以代入01背包，sum(P)就是背包容量，dp数组就是有几种方式可以装满背包。即dp[j]的含义：当背包容量为j时，有dp[j]种方式可以装满背包。
- 确定递推公式：dp[j] += dp[j - nums[i]]。假设dp[j]，j 为5。则：
- 已经有一个nums[i] = 1 的话，有 dp[4]种方法 凑成 容量为5的背包。
- 已经有一个nums[i] = 2 的话，有 dp[3]种方法 凑成 容量为5的背包。
- 已经有一个nums[i] = 3 的话，有 dp[2]中方法 凑成 容量为5的背包。
- 已经有一个nums[i] = 4 的话，有 dp[1]中方法 凑成 容量为5的背包。
- 已经有一个nums[i] = 5 的话，有 dp[0]中方法 凑成 容量为5的背包。
- dp数组初始化：dp[0] = 1；因为递推数组需要叠加，等于0的话就没意义了。可以理解为背包容量为0时，只有一种方式就是放入0可以装包背包。
- 确定遍历顺序：nums放在外循环，sum(P)在内循环，且内循环倒序。
code
class Solution {
/**
* @param Integer[] $nums
* @param Integer $target
* @return Integer
*/
function findTargetSumWays($nums, $target) {
$sum = 0;
$len = count($nums);
for($i = 0; $i < $len; $i++) $sum += $nums[$i];
//如果target大于数组之和就没意义
if(abs($target) > $sum) return 0;
//（$target + $sum）/2为小数的话，整数数组没有组合可以组成小数
if(($target + $sum) % 2 == 1) return 0;
//求得背包容量sum(P)
$bagweight = ($target + $sum) / 2;
$dp = [];
$dp[0] = 1;
for($i = 0; $i < $len; $i++){
for($j = $bagweight; $j >= $nums[$i]; $j--){
//累加
$dp[$j] += $dp[$j- $nums[$i]];
}
}
return $dp[$bagweight];
}
}复杂度
时间复杂度
O(n × m)，n为正数个数，m为背包容量
空间复杂度
O(m)，m为背包容量
474. 一和零
解题方法
- 思路：本题比之前的题目更抽象，因为这题的背包是一个二维的背包，背包内容为m个0,0个1，以及x个子集。所以dp数组抽象出来的含义就是：dp[i][j]：代表背包里装了i个0,j个1,存在最多的子集数是dp[i][j]。
- 确定递推公式：常规的递推公式：dp[j] = max(dp[j], dp[j-weight[i]] + val[i]);根据dp数组含义推演二维得到：dp[i][j] = max(dp[i][j], dp[i-zeroNum][j- oneNum] + 1)，字符串的zeroNum和oneNum相当于物品的重量（weight[i]），字符串本身的个数相当于物品的价值（value[i]）。
- i-zeroNum表示当前背包减去0的个数，
- j-oneNum表示当前背包减去1的个数。
- dp[i - zeroNum][j - oneNum]表示背包-当前物品的重量（0,1的个数）
- +1，是增加了一个子集的意思
- dp数组初始化：初始化为0即可。因为物品价值不会是负数，初始为0，保证递推的时候dp[i][j]不会被初始值覆盖。
- 遍历顺序：外层遍历物品（strs数组就是物品），内层循环0,1的个数。
code
class Solution {
/**
* @param String[] $strs
* @param Integer $m
* @param Integer $n
* @return Integer
*/
function findMaxForm($strs, $m, $n) {
//dp[i][j]：最多有i个0和j个1的strs的最大子集的大小为dp[i][j]。
$dp = [];
//初始化数组
for($i = 0; $i <= $m; $i++){
for($j = 0; $j <= $n; $j++){
$dp[$i][$j] = 0;
}
}
foreach($strs as $str){
$zeroNum = $oneNum = 0;
//计算0,1的个数
for($k = 0; $k < strlen($str); $k++){
if($str[$k] == 0) $zeroNum++;
else $oneNum++;
}
for($i = $m; $i >= $zeroNum; $i--){
for($j = $n; $j >= $oneNum; $j--){
//递推公式，$dp[$i-$zeroNum][$j-$oneNum] + 1 。$i-$zeroNum表示减去0的个数，$j-$oneNum减去1的个数。
//加起来dp[i - zeroNum][j - oneNum]表示背包-当前物品的重量（0,1的个数）+1，是增加了一个子集的意思
$dp[$i][$j] = max($dp[$i][$j], $dp[$i-$zeroNum][$j-$oneNum] + 1);
}
}
}
return $dp[$m][$n];
}
}复杂度
时间复杂度
O(kmn)，k 为strs的长度
空间复杂度
O(mn)
本作品采用《CC 协议》，转载必须注明作者和本文链接
关于 LearnKu
粤公网安备 44030502004330号