【力扣刷题】_背包问题汇总

发表于 | 分类于

背包问题汇总

背包问题分类与结题模板

背包问题就是给定一个数组nums，按照一定方式从中选取元素，使其组成背包容量target的问题。

背包问题按数组元素选取规则可以分为：

  • 0/1背包：每个元素最多选取一次；
  • 完全背包：每个元素可以复选；
  • 组合背包：元素选取需要考虑顺序。

背包问题按照求解目的可以分为：

  • 最值问题：求选取元素个数或其价值的最大值或最小值；
  • 存在问题：求是否存在满足该条件的元素组合；
  • 组合问题：求所有满足该要求的不同元素组合。

背包问题的固定解法就是动态规划，解题模板是两层循环，分别遍历数组nums和背包容量target，然后写状态转移方程。根据求解目的可以确定状态转移方程。

状态转移方程的选择：

  • 最值问题: dp[i] = max/min(dp[i], dp[i-num]+1)或dp[i] = max/min(dp[i], dp[i-num]+num)；
  • 存在问题(boolean)：dp[i]=dp[i]||dp[i-num]；
  • 组合问题：dp[i]+=dp[i-num]。

leetcode背包问题总结：

0/1背包：

  • 416.分割等和子集
  • 474.一和零
  • 494.目标和
  • 879.盈利计划
  • 1049.最后一块石头的重量2

完全背包：

  • 279.完全平方数
  • 322.零钱兑换
  • 377.组合总和4
  • 518.零钱兑换2
  • 1449.数位成本和为目标值的最大数字

组合背包：

  • 1155.郑骰子的N中方法

【力扣刷题】_279.完全平方数

279.完全平方数

  • 代码：

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    public class leetcode0279 {
        public int numSquares(int n) {
            //dp[i]表示和为i的完全平方数的最小个数
            int[] dp = new int[n + 1];

            //赋初值
            for (int i = 0; i <= n; i++) {
                dp[i] = i;
            }

            for (int i = 2; i <= n; i++) {
                for (int j = 1; j * j <= i; j++) {
                    dp[i] = Math.min(dp[i],dp[i - j * j] + 1);
                }
            }

            return dp[n];
        }
    }

【力扣刷题】_322.零钱兑换

322.零钱兑换

  • 代码：

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    public class leetcode0322 {
        public int coinChange(int[] coins, int amount) {
            int[] dp = new int[amount + 1];

          	//使状态初始值都为一个明显不可能的值，最后看状态值是否改变，改变了即说明存在兑换方案。
            for (int i = 1; i <= amount; i++) {
                dp[i] = amount + 1;
            }

            int n = coins.length;
            for (int i = 0; i <= amount; i++) {
                for (int j = 0; j < n; j++) {
                    if (coins[j] > i) continue;
                    dp[i] = Math.min(dp[i],dp[i - coins[j]] + 1);
                }
            }

            return dp[amount] == amount + 1 ? -1 : dp[amount];
        }
    }

【力扣刷题】_377.组合综合4

377.组合综合4

  • 代码：

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    public class leetcode0377 {
        public int combinationSum4(int[] nums, int target) {
            int[] dp = new int[target + 1];
            int n = nums.length;
            dp[0] = 1;
            for (int i = 1; i <= target; i++) {
                for (int j = 0; j < n; j++) {
                    if (nums[j] > i) continue;
                    dp[i] += dp[i - nums[j]];
                }
            }
            return dp[target];
        }
    }

【力扣刷题】_416.分割等和子集(非常重要)

416.分割等和子集

  • 本题的难点在于理解题意，要能看懂这是一道背包问题。

  • 0-1背包问题一定要先从二维动态规划来理解，再简化写成一维动态规划。

  • 以容量target为内循环时，一定要从后往前循环，因为每次计算一个状态dp时需要依据的是上一行的两个状态值，如果从前往后会导致状态dp[j - num[i]]不是上一行状态，而是本行状态。

  • 代码：

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    public class leetcode0416 {
        public boolean canPartition(int[] nums) {
            int sum = 0;
            int n = nums.length;
            for (int i = 0; i < n; i++) {
                sum += nums[i];
            }
            int flag = sum % 2;
            if (flag == 1) return false;
            int target = sum / 2;

            boolean[] dp = new boolean[target + 1];
            dp[0] = true;
            for (int i = 0; i < n; i++) {
                //此处必须为从后往前遍历，这样才能保证状态dp[j - nums[i]]为上一行的状态，而不是本行已经改变了状态值。
                for (int j = target; j >= nums[i]; j--) {
                    dp[j] = dp[j] || dp[j - nums[i]];
                }
            }
            return dp[target];
        }
    }

【力扣刷题】_474.一和零(非常重要)

474.一和零

  • 这是一个背包不要求装满，要求撞到最大值的0/1背包问题。

  • 代码：

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    public class leetcode0474 {
        public int findMaxForm(String[] strs, int m, int n) {
            //先统计每个字符串中0和1的个数
            int len = strs.length;
            int[][] scope = new int[len][2];
            for (int i = 0; i < len; i++) {
                for (int j = 0; j < strs[i].length(); j++) {
                    if (strs[i].charAt(j) == '0') {
                        scope[i][0]++;
                    }else {
                        scope[i][1]++;
                    }
                }
            }

            //状态dp[i][j]为0个数最多为i个，1个数最多为j个时最大子集的大小。
            int[][] dp = new int[m + 1][n + 1];
            for (int i = 0; i < len; i++) {
                for (int j = m; j >= scope[i][0]; j--) {
                    for (int k = n; k >= scope[i][1]; k--) {
                        dp[j][k] = Math.max(dp[j][k],dp[j - scope[i][0]][k - scope[i][1]] + 1);
                    }
                }
            }
            return dp[m][n];
        }
    }

【力扣刷题】_494.目标和

494.目标和

  • 递归：bfs，递归的话时间复杂度较大，此处时间复杂度为O(2^n)。

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    public class leetcode0494 {
        public int findTargetSumWays(int[] nums, int target) {
            return bfs(nums,0,target,0);
        }

        public int bfs(int[] nums,int index,int target,int sum) {
            if (index == nums.length) {
                if (target == sum) return 1;
                else return 0;
            }
            return bfs(nums,index + 1,target,sum + nums[index]) + bfs(nums,index + 1,target,sum - nums[index]);
        }
    }

  • 迭代：动态规划，此处优化逻辑较为复杂，只提供二维动态规划解法。

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    public class leetcode0494 {
        public int findTargetSumWays(int[] nums, int target) {
            int n = nums.length;
            int sum = 0;
            for (int i = 0; i < n; i++) {
                sum += nums[i];
            }

            if (target > sum || target < - sum) return 0;

            //本题设计到减号，这样的话动态规划状态边界应设为最大值和最小值
            int[][] dp = new int[n][sum * 2 + 1];

            //初始化
            if (nums[0] == 0) {
                dp[0][sum] = 2;
            }else {
                dp[0][sum - nums[0]] = 1;
                dp[0][sum + nums[0]] = 1;
            }

            for (int i = 1; i < n; i++) {
                for (int j = 0; j < sum * 2 + 1; j++) {
                    //计算结果j可能是j-nums[i]加上nums[i]得到的，也可能是j+nums[i]减去nums[i]得到的。
                    //先判断是否查出范围，然后将两种情况的种数相加即可。
                    int plus = (j - nums[i] >= 0) ? dp[i - 1][j - nums[i]] : 0;
                    int mimus = (j + nums[i] <= sum * 2) ? dp[i - 1][j + nums[i]] : 0;
                    dp[i][j] = plus + mimus;
                }
            }

            return dp[n - 1][sum + target];
        }
    }

【力扣刷题】_518.零钱兑换2(非常重要)

518.零钱兑换2

  • 本题的特殊之处在于，硬币可以复用，但是硬币使用顺序不同的情况看做同一种，所以在每种组合方法中最好保证每个硬币连续复用，之后就不再使用该硬币。

  • 代码：

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    public class leetcode0518 {
        public int change(int amount, int[] coins) {
            int n = coins.length;
            int[] dp = new int[amount + 1];

            //计算种数的背包问题，和为0的状态初始化种数为1。
            dp[0] = 1;

            for (int i = 0; i < n; i++) {
                //这里这个顺序遍历非常厉害呀，顺序遍历就把每个元素复用多次的情况加进来了，但是相同元素只能连续使用多次。
                for (int j = coins[i]; j < amount + 1; j++) {
                    dp[j] = dp[j] + dp[j - coins[i]];
                }
            }
            return dp[amount];
        }
    }

【力扣刷题】_879.盈利计划(未解决)

879.盈利计划

  • 反正我目前是连答案都看不懂

  • 代码：

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    public class leetcode0879 {
        public int profitableSchemes(int n, int minProfit, int[] group, int[] profit) {
            int len = group.length;

            //状态dp[i][j][k]表示在有前i+1个工作时，使用员工小于或等于j个、盈利大于或等于k时，的工作计划种数。
            int[][] dp = new int[n + 1][minProfit + 1];

            //背包问题的初始化都非常重要
            for (int i = 0; i < n + 1; i++) {
                dp[i][0] = 1;
            }

            //状态转移方程
            for (int i = 0; i < len; i++) {
                for (int j = n; j >= group[i]; j--) {
                    for (int k = minProfit; k >= 0; k--) {
                      	//没看懂答案此处为何Math.max(0,k - profit[i])
                        dp[j][k] = dp[j][k] + dp[j - group[i]][Math.max(0,k - profit[i])];
                    }
                }
            }

            return dp[n][minProfit];
        }
    }

【力扣刷题】_1049.最后一块石头的重量2

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

  • 本题的难点在于想到并转化为背包问题。其实和分割等和子集有点类似，只不顾此处不一定是二等分，而是找到分成两份的最小差值。

  • 代码：

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    public class leetcode1049 {
        public int lastStoneWeightII(int[] stones) {
            int n = stones.length;
            int sum = 0;
            for (int i = 0; i < n; i++) {
                sum += stones[i];
            }

            int target = sum / 2;
            //状态dp[i]表示元素所能组成的不大于i的最大值
            int[] dp = new int[target + 1];

            for (int i = 0; i < n; i++) {
                for (int j = target; j >= stones[i]; j--) {
                    dp[j] = Math.max(dp[j],dp[j - stones[i]] + stones[i]);
                }
            }
            return sum - dp[target] * 2;
        }
    }

【力扣刷题】_1155.掷骰子的N中方法

1155.掷骰子的N中方法

  • 代码

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    public class leetcode1155 {
        public int numRollsToTarget(int d, int f, int target) {
            //状态
            int[] dp = new int[target + 1];
            
            //初始化
            dp[0] = 1;
            
            //状态转移方程
            for (int i = 0; i < d; i++) {
                for (int j = target; j >= 0; j--) {
                    int sum = 0;
                    for (int k = 1; k <= f; k++) {
                        if (k > j) break;
                        sum = sum + dp[j - k];
                    }
                    dp[j] = sum;
                }
            }
            return dp[target];
        }
    }

【力扣刷题】_1449.数位成本和为目标值的最大数字(未解决)

1449.数位成本和为目标值的最大数字