代码随想录算法训练营第三十五天 | leetcode：最后一块石头的重量 II,目标和,一和零

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];
    }
}