LeetCode刷题—动态规划(四)

刷了几道背包问题,用了一周时间,动态规划的难真的领会到了。虽然一变就不会,还是想总结一下,加深理解。

0-1背包

引入
416,分割等和子集,medium
494,目标和,medium
474,一和零,medium
总结

引入

一个可装载重量为W的背包和N个物品,每个物品有重量和价值两个属性。怎么装使这个背包装下物品的价值最大?

套路

  1. 子问题二维 dp 数组 d p [ i ] [ j ] dp[i][j] dp[i][j]—对于前 i 个物品,当前背包容量为 j,这种情况下可以装的最大价值是 d p [ i ] [ j ] dp[i][j] dp[i][j]

    比如说,如果 d p [ 3 ] [ 5 ] = 6 dp[3][5] = 6 dp[3][5]=6,其含义为:对于给定的一系列物品中,若只对前 3 个物品进行选择,当背包容量为 5 时,最多可以装下的价值为 6。
    根据这个定义,我们想求的最终答案就是 dp[N][W]

  2. base case: 当没有物品 或 背包没有容量时, d p [ 0 ] [ . . . ] = d p [ . . . ] [ 0 ] = 0 dp[0][...] = dp[...][0] = 0 dp[0][...]=dp[...][0]=0

  3. 状态转移

    物品 i 有两种选择—装进背包和不装,设第 i 件物品体积为 w,价值为 v。

    • 物品 i 不装进背包,最大价值 d p [ i ] [ j ] = d p [ i − 1 ] [ j ] dp[i][j] = dp[i - 1][j] dp[i][j]=dp[i1][j]
    • 物品 i 装进背包,最大价值 d p [ i ] [ j ] = d p [ i − 1 ] [ j − w ] + v dp[i][j] = dp[i - 1][j - w] + v dp[i][j]=dp[i1][jw]+v

    因此,0-1 背包的状态转移方程为:

    d p [ i ] [ j ] = M a t h . m a x ( d p [ i − 1 ] [ j ] , d p [ i − 1 ] [ j − w ] + v ) dp[i][j] = Math.max(dp[i - 1][j],dp[i - 1][j - w] + v) dp[i][j]=Math.max(dp[i1][j],dp[i1][jw]+v)

代码:

// W 为背包总体积
// N 为物品数量
// weights 数组存储 N 个物品的重量
// values 数组存储 N 个物品的价值
public int knapsack(int W, int N, int[] weight, int[] values){
 //dp[i][j]表示装 i 个物品背包容量为 j
 int[][] dp = new int[N + 1][W + 1];
 //默认初始化都为0,从第1行和第1列开始赋值
 for(int i = 1; i < N + 1; i++){
     //物品从weight[0]开始添加,w表示第i个物品的体积,v表示第i个物品的价值
     int w = weight[i - 1]; int v = values[i - 1];
     for(int j = 1; j < W + 1; j++){
         // 装入或者不装入背包,择优
         if(j >= w)
         	dp[i][j] = Math.max(dp[i - 1][j],dp[i - 1][j - w] + v);
         // 当前背包容量装不下,只能选择不装入背包
         else
             dp[i][j] = dp[i - 1][j];
     }
 }
 return dp[N][W];
}

注意到 d p [ i ] [ j ] dp[i][j] dp[i][j] 都是通过上一行 d p [ i − 1 ] [ . . ] dp[i-1][..] dp[i1][..] 转移过来的,之前的数据都不会再使用了。
所以,我们可以进行状态压缩,将二维 dp 数组压缩为一维,节约空间复杂度,可见下一题。

416,分割等和子集,medium

给定一个只包含正整数的非空数组。是否可以将这个数组分割成两个子集,使得两个子集的元素和相等。

注意:

每个数组中的元素不会超过 100
数组的大小不会超过 200
示例 1:

输入: [1, 5, 11, 5]

输出: true

解释: 数组可以分割成 [1, 5, 5] 和 [11].

示例 2:

输入: [1, 2, 3, 5]

输出: false

解释: 数组不能分割成两个元素和相等的子集.
  • 题意分析:

    看起来和背包没关系,实际是背包问题的变体:子集背包问题。原背包问题的二维数组 v = d p [ i ] [ j ] v = dp[i][j] v=dp[i][j] 表示 对于前 i 个物品,当前背包容量为 j,这种情况下可以装的最大价值是 v v v

    此题中,要把数组分割成两个等和子集,即背包容量:数组的和 sum的一半,物品:数组元素。如果遍历数组,部分元素的和恰好为 背包容量,则剩余元素的和也恰好为 sum / 2,返回true。

  • 思路:

    特殊情况:

    nums 数组的元素和 sum 若为奇数,则无法分割,返回false。

    如果 n < 2,数组无法分割,返回false。

  1. 子问题

    x = d p [ i ] [ j ] x = dp[i][j] x=dp[i][j] 表示 对于数组nums 的前 i 个元素,当前元素和是否为 j, 若为 j , x = t r u e x = true x=true;否则, x = f a l s e x = false x=false

  2. base case

    d p [ 0 ] [ . . . ] = f a l s e dp[0][...] = false dp[0][...]=false 数组中没有元素可选取,返回false。

    d p [ . . . ] [ 0 ] = t r u e dp[...][0] = true dp[...][0]=true 目标元素和为 0,不选取元素即可。

  3. 状态转移方程

    当前元素 num = nums[i - 1](从数组的 第 0 个元素开始遍历)

    ①. j >= num

    • 不将 num 算入,能否恰好等于 j , d p [ i ] [ j ] dp[i][j] dp[i][j]取决于 d p [ i − 1 ] [ j ] dp[i - 1][j] dp[i1][j]

    • num 算入,能否恰好等于 j , d p [ i ] [ j ] dp[i][j] dp[i][j]取决于 d p [ i − 1 ] [ j − n u m ] dp[i - 1][j - num] dp[i1][jnum]

      理解:如果装入第 i 个元素,要看剩余元素和 j - num 限制下是否恰好装满。

    ②.j < num

    要达到的元素和 比 当前元素值 小,无法加入。

    总结:
    在这里插入图片描述

  • 代码:

    class Solution {
        public boolean canPartition(int[] nums) {
            int n = nums.length;
            if(n < 2) return false;
            int sum = 0;
            for(int num : nums){
                sum += num;            
            }
            if(sum % 2 != 0) return false;
            int target = sum / 2;
            //dp[i][j]— [0, i]元素 元素是否为 j
            boolean[][] dp = new boolean[n + 1][target + 1];//初始化都为false
            //base case
            for(int i = 0; i < n ; i++){
                dp[i][0] = true;
            }
            for(int i = 1; i < n + 1; i++){
                int num = nums[i - 1];
                for(int j = 1; j < target + 1; j++){
                    //要达到的元素和 比 当前元素值 小,无法加入
                    if(j < num) dp[i][j] = dp[i - 1][j];
                    else dp[i][j] = dp[i - 1][j] | dp[i - 1][j - num];
                }
            }
            return dp[n][target];
        }
    }
    
  • 降维

    d p [ i ] [ j ] dp[i][j] dp[i][j] 都是通过上一行 d p [ i − 1 ] [ . . ] dp[i-1][..] dp[i1][..] 转移过来的,可以进行状态压缩,将二维 dp 数组压缩为一维,但要注意 j 应该从后往前反向遍历,因为每个物品(或者说数字)只能用一次,以免之前的结果影响其他的结果。

    • 代码
    class Solution {
      public boolean canPartition(int[] nums) {
          int n = nums.length;
          int sum = 0;
          for(int num : nums){
              sum += num; 
          }
          //特殊:
          if(sum % 2 != 0) return false;
          if(n < 2) return false;
          sum = sum / 2;
          boolean[] dp = new boolean[sum + 1];
          dp[0] = true;
           for(int i = 1; i <= n; i++){
              int num = nums[i - 1];
              for(int j = sum; j > 0; j--){
                  if(j >= num)
                      dp[j] = dp[j] | dp[j - num];
              }
          }
          return dp[sum];
      }
    }
    

总结做题步骤

  1. 理解题意,判定此题为 0-1背包问题

  2. 此题是否有特殊情况

  3. 动态规划正常做法
    1. 子问题:确定背包和物品指代什么, d p [ i ] [ j ] dp[i][j] dp[i][j] 返回值是什么
    2. base case:通常为 d p [ 0 ] [ . . . ] 、 d p [ . . . ] [ 0 ] 、 d p [ 0 ] [ 0 ] dp[0][...]、dp[...][0]、dp[0][0] dp[0][...]dp[...][0]dp[0][0]
    3. 状态转移方程:
    先遍历物品,再遍历背包。每个物品只有装和不装两个选择。

    组合问题公式   dp[i] += dp[i - num]
    True、False问题公式    dp[i] = dp[i] or dp[i - num]
    最大最小问题公式    dp[i] = min(dp[i], dp[i - num]+1) 或 dp[i] =  max(dp[i], dp[i - num]+1)
    
  4. 最终返回结果

  5. 状态压缩至一维(可不进行)

494,目标和,medium

给定一个非负整数数组a1, a2, ..., an 和一个目标数 S。现在你有两个符号 + 和 -。对于数组中的任意一个整数,你都可以从 + 或 -中选择一个符号添加在前面。

返回可以使最终数组和为目标数 S 的所有添加符号的方法数。

示例:

输入:nums: [1, 1, 1, 1, 1], S: 3
输出:5
解释:

-1+1+1+1+1 = 3
+1-1+1+1+1 = 3
+1+1-1+1+1 = 3
+1+1+1-1+1 = 3
+1+1+1+1-1 = 3

一共有5种方法让最终目标和为3。
提示:
 数组非空,且长度不会超过 20 。
   初始的数组的和不会超过 1000 。
  保证返回的最终结果能被 32 位整数存下。
  • 题意分析:
    在这里插入图片描述
    则转换为 0-1背包问题:给定一个数组 和一个容量为 target 的背包,求多少种方式将背包填满。

  • 思路:

  1. 子问题

    x = d p [ i ] [ j ] x = dp[i][j] x=dp[i][j] 表示 对于数组nums 的前 i 个元素,放进容量 j 的背包,装满方式为 x。

    特殊情况:

    S + sum 必须为偶数才可分解,S < sum 才可使数组 nums 元素得到 S

  2. base case

    d p [ 0 ] [ 0 ] = 1 dp[0][0] = 1 dp[0][0]=1 没有元素,所以只能不选,和为0

  3. 状态转移方程

    当前元素 num = nums[i - 1](从数组的 第 0 个元素开始遍历)

    ①. j >= num

    将 当前 num = nums[i-1] 放入或不放入背包, d p [ i ] [ j ] = d p [ i − 1 ] [ j ] + d p [ i − 1 ] [ j − n u m ] dp[i][j] = dp[i-1][j]+dp[i-1][j-num] dp[i][j]=dp[i1][j]+dp[i1][jnum]

    ②. j < num

    不能放入,取决于上一状态, d p [ i ] [ j ] = d p [ i − 1 ] [ j ] dp[i][j] = dp[i-1][j] dp[i][j]=dp[i1][j]

  • 代码:

    class Solution {
      public int findTargetSumWays(int[] nums, int S) {
          int sum = 0;
            for(int num : nums){
                sum += num;
            }
            //特殊情况
            if(S > sum || (sum + S) % 2 == 1) return 0;
           
            int target = (sum + S) / 2;
            int[][] dp = new int[nums.length + 1][target + 1]; 
            //base case
            dp[0][0] = 1;
    
            // 状态转移方程
            for(int i = 1; i < nums.length + 1; i++){
                int num = nums[i - 1];
                for(int j = 0; j < target + 1; j++){
                    if(j >= num)
                        dp[i][j] = dp[i - 1][j] + dp[i - 1][j - num];
                    else
                        dp[i][j] = dp[i - 1][j];
                }
            }
            return dp[nums.length][target];
        }
    }
    
  • 对base case 的理解:

    注意与0-1背包的区别:

    对于0-1 背包,物品大小为正数,可以先对二维数组初始化第0行(除 [ 0 ] [ 0 ] [0][0] [0][0] 位置外全为0)和第0列(全为1)。然后 i 和 j 都从1开始遍历。
    对于该问题,列表中可能存在为 0 的元素,因此选不选这个0,都能将容量为0的背包装满。如,nums={0,0},target=0,dp[2][0]≠1

    所以base case 只有 d p [ 0 ] [ 0 ] = 1 dp[0][0]=1 dp[0][0]=1, 剩下的第0列的其他位置的值用状态转移方程确定 (而不能将 d p [ i ] [ 0 ] dp[i][0] dp[i][0]初始化为1) 。即 i 从1开始遍历,j 从0开始遍历。

  • 优化:将二维dp数组压缩为一维,dp[i][j]都是通过上一行dp[i-1][..]转移过来的,之前的数据都不会再使用了。需要注意的是 j应该从后往前反向遍历,因为每个物品(数字)只能用一次,以免之前的结果影响其他的结果。

    1. 子问题:

      x = d p [ i ] x = dp[i] x=dp[i] 表示数组 nums 的元素 装满 容量为 i 的背包,有 x 种装法。

    2. base case

      d p [ 0 ] = 1 dp[0] = 1 dp[0]=1 全部不装,一种装法。

    3. 状态转移方程

      由上面的二维可得$ dp[j] = dp[j] + dp[j - num]$

    class Solution {
        public int findTargetSumWays(int[] nums, int S) {
            int sum = 0;
            for(int num : nums){
                sum += num;
            }
            //特殊情况
            if(S > sum || (sum + S) % 2 == 1) return 0;
           
            int target = (sum + S) / 2;
    		int[] dp = new int[target + 1]; 
            //base case//放入背包重量为0的方案数为1,不选
            dp[0] = 1;
            for(int i = 1; i < nums.length + 1; i++){
                int num = nums[i - 1];
                for(int j = target; j >= 0; j--){
                    if(j >= num)
                        dp[j] = dp[j] + dp[j - num];
                }
            }
            return dp[target];
        }
    }
    
  • 另一种方法:递归

    对于第 i 个数,可以 ‘+’ 或 ‘-’,分别递归搜索两种操作,当搜索完一遍,如果元素和sum等于S,count+1。、

    class Solution {
      int count = 0;
      public int findTargetSumWays(int[] nums, int S) {
          return helper(nums, 0, 0, S);
      }
      public int helper(int[] nums, int i, int sum, int S) {
          if(i == nums.length){
              if(sum == S)
                  count++;
          }
          else{
              //还没全部搜索完,递归两种情况
              helper(nums, i + 1, sum + nums[i], S);
              helper(nums, i + 1, sum - nums[i], S);
          }
          return count;
      }
    }
    

474,一和零,medium

给你一个二进制字符串数组 strs 和两个整数 m 和 n 。

请你找出并返回 strs 的最大子集的大小,该子集中 最多 有 m 个 0 和 n 个 1 。

如果 x 的所有元素也是 y 的元素,集合 x 是集合 y 的 子集 。

示例 1:

输入:strs = ["10", "0001", "111001", "1", "0"], m = 5, n = 3
输出:4
解释:最多有 5 个 0 和 3 个 1 的最大子集是 {"10","0001","1","0"} ,因此答案是 4 。
其他满足题意但较小的子集包括 {"0001","1"} 和 {"10","1","0"} 。{"111001"} 不满足题意,因为它含 4 个 1 ,大于 n 的值 3 。

示例 2:

输入:strs = ["10", "0", "1"], m = 1, n = 1
输出:2
解释:最大的子集是 {"0", "1"} ,所以答案是 2 。

提示:

1 <= strs.length<= 600
1 <= strs[i].length <= 100
strs[i] 仅由 ‘0’ 和 ‘1’ 组成
1 <= m, n <= 100

  • 题目解析:

    仍然是 0-1背包问题,但此题的背包有两个,一个放0,一个放1,称为背包0 和 背包1。物品:字符串数组中的字符。为最大最小问题。

  • 思路:

    1. 子问题

      d p [ i ] [ j ] [ k ] dp[i][j][k] dp[i][j][k] — 前 i 个字符串将 背包0容量为 j,背包1容量为k 的最大子集大小

    2. base case

      d p [ 0 ] [ . . . ] [ . . . ] = 0 dp[0][...][...]=0 dp[0][...][...]=0 如果不使用任何一个字符串,则背包能装的字符串数就为0。

      d p [ . . . ] [ 0 ] [ 0 ] = 0 dp[...][0][0]=0 dp[...][0][0]=0 如果背包0,背包1的容量都为0,它能装的字符串数也为0。

    3. 状态转移方程

      当前字符串str

      • 如果字符串str不装入背包,受上一状态影响。

        d p [ i ] [ j ] [ k ] = d p [ i − 1 ] [ j ] [ k ] dp[i][j][k]=dp[i-1][j][k] dp[i][j][k]=dp[i1][j][k]

      • 如果字符串str 装入背包,则与不装入的选择取最大值。

        d p [ i ] [ j ] [ k ] = m a x ( d p [ i − 1 ] [ j ] [ k ] , d p [ i − 1 ] [ j − c o u n t 0 ] [ j − c o u n t 1 ] + 1 ) dp[i][j][k] = max(dp[i-1][j][k],dp[i-1][j-count_0][j-count_1] + 1) dp[i][j][k]=max(dp[i1][j][k],dp[i1][jcount0][jcount1]+1)

      边界条件为 j 与 str 中0 的数量 的大小关系,k 与 str 中 1 的数量的大小关系。

    4. 返回 d p [ l e n ] [ m ] [ n ] dp[len][m][n] dp[len][m][n]

  • 代码:

    class Solution {
        public int findMaxForm(String[] strs, int m, int n) {
            int len = strs.length;
            int[][][] dp = new int[len + 1][m + 1][n + 1];
            //base case dp[0][...][...]=0、dp[...][0][0]=0
            
            //先循环物品
            for(int i = 1; i < len + 1; i++){
                String str = strs[i - 1];
                for(int j = 0; j < m + 1; j++){
                    for(int k = 0; k < n + 1; k++){
                        if(j < count_0(str) || k < count_1(str))
                        dp[i][j][k] = dp[i - 1][j][k];
                        else
                        dp[i][j][k] = Math.max(dp[i - 1][j][k], dp[i - 1][j - count_0(str)][k - count_1(str)] + 1);
                    }
                }
            }
            return dp[len][m][n];
        }
        //统计str中0和1的个数
        public int count_0(String str){
            char[] str_c = str.toCharArray();
            int count = 0;
            for(char c : str_c){
                if(c == '0') count++;
            }
            return count;
        } 
         public int count_1(String str){
            char[] str_c = str.toCharArray();
            int count = 0;
            for(char c : str_c){
                if(c == '1') count++;
            }
            return count;
        } 
    }
    
  • 状态压缩:

    class Solution {
        public int findMaxForm(String[] strs, int m, int n) {
            int len = strs.length;
            int[][] dp = new int[m + 1][n + 1];
            for(int i = 1; i < len + 1; i++){
                String str = strs[i - 1];
                for(int j = m; j >= count_0(str); j--){
                    for(int k = n; k >= count_1(str); k--){
                        dp[j][k] = Math.max(dp[j][k], dp[j - count_0(str)][k - count_1(str)] + 1);
                    }
                }
            }
            return dp[m][n];
        }
        //统计str中0和1的个数
        public int count_0(String str){
            char[] str_c = str.toCharArray();
            int count = 0;
            for(char c : str_c){
                if(c == '0') count++;
            }
            return count;
        } 
         public int count_1(String str){
            char[] str_c = str.toCharArray();
            int count = 0;
            for(char c : str_c){
                if(c == '1') count++;
            }
            return count;
        } 
    }
    
  • 思考:为什么背包0 和 背包1的 j、k要从 0 开始遍历?

    字符串数组中如果存在“00”,“00”,选择也是不同的,会影响 d p dp dp 数组的结果。可参考494题中对 base case 的理解。

总结

做题步骤:

  1. 理解题意,判定此题为 0-1背包问题

  2. 此题是否有特殊情况

  3. 动态规划正常做法
    1. 子问题:确定背包和物品指代什么, d p [ i ] [ j ] dp[i][j] dp[i][j] 返回值是什么
    2. base case:通常为 d p [ 0 ] [ . . . ] 、 d p [ . . . ] [ 0 ] 、 d p [ 0 ] [ 0 ] dp[0][...]、dp[...][0]、dp[0][0] dp[0][...]dp[...][0]dp[0][0]
    3. 状态转移方程:
    先遍历物品,再遍历背包。每个物品只有装和不装两个选择。

    组合问题公式   dp[i] += dp[i - num]
    True、False问题公式    dp[i] = dp[i] or dp[i - num]
    最大最小问题公式    dp[i] = min(dp[i], dp[i - num]+1) 或 dp[i] =  max(dp[i], dp[i - num]+1)
    
  4. 最终返回结果

  5. 状态压缩至一维(可不进行)

套模板还是有用的,难的部分在于理清题意再转化到模板。base case 的情况容易混淆,分不清的时候先写出多维dp数组,再进行降维可能还有助于做题。
完全背包问题请见下一节总结内容。