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

1049. 最后一块石头的重量 II

解题方法

  1. 思路:尽量让石头分成重量相同的两堆,相撞之后剩下的石头最小。背包容量为sum/2,这里有个小细节,有小数时,需要向下取整,这样sum - dp[target] 一定是大于等于dp[target]的。物品就是石头,石头的价值与重量都是stones[i]。这样就把问题转换成背包问题了。
  2. 确定dp数组以及下标的含义:dp[j]表示容量(这里说容量更形象,其实就是重量)为j的背包,最多可以背最大重量为dp[j]。
  3. 确定递推公式:dp[j] = max(dp[j], dp[j - weight[i]] + value[i]);
  4. 既然 dp[j]中的j表示容量,那么最大容量(重量)是多少呢,就是所有石头的重量和。因为提示中给出1 <= stones.length <= 30,1 <= stones[i] <= 100,所以最大重量就是30 * 100 。而我们要求的target其实只是最大重量的一半,所以dp数组开到1500大小就可以了。值全部初始化为0即可。
  5. 确定遍历顺序:物品遍历的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数组。

  1. 数学公式推导:假设: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为非负整数数组,而整数没办法组合成小数。
  2. 由上面数学公式可以得出:计算出需要设为正数和为sum(P)有几种方式,就是最终需要求得的结果。那么就可以代入01背包,sum(P)就是背包容量,dp数组就是有几种方式可以装满背包。即dp[j]的含义:当背包容量为j时,有dp[j]种方式可以装满背包
  3. 确定递推公式: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的背包。
  4. dp数组初始化:dp[0] = 1;因为递推数组需要叠加,等于0的话就没意义了。可以理解为背包容量为0时,只有一种方式就是放入0可以装包背包。
  5. 确定遍历顺序: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. 一和零

解题方法

  1. 思路:本题比之前的题目更抽象,因为这题的背包是一个二维的背包,背包内容为m个0,0个1,以及x个子集。所以dp数组抽象出来的含义就是:dp[i][j]:代表背包里装了i个0,j个1,存在最多的子集数是dp[i][j]。
  2. 确定递推公式:常规的递推公式: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,是增加了一个子集的意思
  3. dp数组初始化:初始化为0即可。因为物品价值不会是负数,初始为0,保证递推的时候dp[i][j]不会被初始值覆盖。
  4. 遍历顺序:外层遍历物品(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 协议》,转载必须注明作者和本文链接
《L03 构架 API 服务器》
你将学到如 RESTFul 设计风格、PostMan 的使用、OAuth 流程,JWT 概念及使用 和 API 开发相关的进阶知识。
《L02 从零构建论坛系统》
以构建论坛项目 LaraBBS 为线索,展开对 Laravel 框架的全面学习。应用程序架构思路贴近 Laravel 框架的设计哲学。
讨论数量: 0
(= ̄ω ̄=)··· 暂无内容!

讨论应以学习和精进为目的。请勿发布不友善或者负能量的内容,与人为善,比聪明更重要!