【LeetCode】动态规划问题：背包问题系列

太过爱你忘了你带给我的痛 2022-10-29 09:13 208阅读 0赞

### 背包问题 ###

*  给定容量和元素，然后让选元素

#### [416. 分割等和子集][416.] ####

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

注意:

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

示例 1:

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

示例 2:

输入: [1, 2, 3, 5]
    输出: false
    解释: 数组不能分割成两个元素和相等的子集.

**题解**

记忆化深搜**不行**，优化到最后还是超时，因为递归树太大了

class Solution { 
       boolean isSuccess;
       public boolean canPartition(int[] nums) { 
           int sum = 0;
           for(int n : nums){ 
               sum += n;
           }
          
           byte[] idxUseingBitmap = new byte[nums.length];
           if(sum % 2 == 0){ 
              Arrays.sort(nums);
              func(nums , 0 , idxUseingBitmap , 0 , sum);
           }
    
           return sum % 2 == 1 ? false : isSuccess;
       }
    
       void func(int[] nums , int idx , byte[] idxUseingBitmap , int nowSum , int sum){ 
           if(nowSum + nums[idx] == sum / 2){ 
               isSuccess = true;
           }
           if(isSuccess || nowSum + nums[idx] > sum / 2){ 
               return;
           }
    
           idxUseingBitmap[idx] = 1;
    
           byte[] findIsAlreadyBuild = new byte[101]; // 避免一个节点下出现同种子节点
           for(int i = nums.length - 1 ; i >= 0 ; i --){  // 数组已经排序了，从小到大，先用大的构建子节点，可以尽早结束
               if(! isSuccess && idxUseingBitmap[i] == 0 && findIsAlreadyBuild[nums[i]] != 1){ 
                   findIsAlreadyBuild[nums[i]] = 1;
                   func(nums , i , idxUseingBitmap , nowSum + nums[idx] , sum);
                   if(isSuccess)  
                       return;
               }
           }
    
           idxUseingBitmap[idx] = 0;
       }
    }

**动态规划**

*  自底向上的
    
     *  数组里每个格子代表的是当前情况（即此刻的容量多少，存在多少种元素）的最优返回值

有两种每次选择最优然后往上递推的办法

*  外层遍历容量 + 内存遍历可选元素；外层遍历可选元素 + 内层遍历容量
    
     *  这两种对于背包问题来说都是完全等价的，只要不出现超前访问就都是可以的（比如 i 是从小到大遍历，但是当前嵌套循环里面执行的代码用到了 i + 1 或者其他比 i 大的索引，那么就是超前访问了，因为还没递推到那）
     *  对于超前访问的唯一解决办法：把要超前访问的属性放在 for 循环最内层，等构成二维表格后，然后把最后一行（也就是递推开始时 i 和 j 初始值对应的那一排）初始化好

对于背包问题的递归公式

*  如果按照自顶向下递归来思考的话，肯定是会转移可选元素中，每一个所需容量小于当前剩余容量（有两种可能，即有没有减去当前遍历到的元素所需的容量）的，但是为什么 dp 只是每次只从不包含当前元素（即 i-1）中选择剩余容量对应的最大的呢
 *  因为上面那种完全所有情况的回溯，实际上递推完全可以简化成剩余容量是否减去了当前元素（即是否选择当前元素）。

class Solution {
       
        public boolean canPartition(int[] nums) {
            int sum  = 0;
            for(int i = 0 ; i < nums.length ; i ++){
                sum += nums[i];
            }
    
            if(sum % 2 != 0){
                return false;
            }
    
            int ac = sum / 2;
            int[][] c = new int[nums.length + 1][ac + 1] ;
    
            for(int i = 1; i <= nums.length ; i ++){
                for(int j = 1 ; j <= ac ; j ++){
                    if(j < nums[i - 1]){
                        c[i][j] = c[i - 1][j];
                    }else {
                        int beforeLevel = c[i - 1][j];
                        int addNow = nums[i - 1] + c[i - 1][j - nums[i - 1]];
                        c[i][j] = beforeLevel > addNow ? beforeLevel : addNow;
                    }
                }
            }
    
            return c[nums.length][ac] == ac ? true : false;
        }
    }

#### [322. 零钱兑换][322.] ####

给定不同面额的硬币 coins 和一个总金额 amount。编写一个函数来计算可以凑成总金额所需的最少的硬币个数。如果没有任何一种硬币组合能组成总金额，返回 -1。

你可以认为每种硬币的数量是无限的。

示例 1：

输入：coins = [1, 2, 5], amount = 11
    输出：3 
    解释：11 = 5 + 5 + 1

示例 2：

输入：coins = [2], amount = 3
    输出：-1

示例 3：

输入：coins = [1], amount = 0
    输出：0

示例 4：

输入：coins = [1], amount = 1
    输出：1

示例 5：

输入：coins = [1], amount = 2
    输出：2

**题解**

class Solution { 
        public int coinChange(int[] coins, int amount) { 
            int[][] dp = new int[coins.length + 1][amount + 1];
            int[][] coinsNum = new int[coins.length + 1][amount + 1];
    
            for(int i = 1 ; i <= coins.length ; i ++){ 
                for(int j = 1 , counter = 0; j <= amount ; j ++){ 
                    if(j % coins[i - 1] == 0){ 
                        counter ++;
                    }
                    int maxValue  = 0 , minNums = Integer.MAX_VALUE;
                    for(int k = 0 ; k <= counter  ; k ++){ 
                        int value = k * coins[i - 1] + dp[i - 1][j - (coins[i - 1] * k)];
                        if(value == maxValue){ 
                            minNums = Math.min(minNums , k + coinsNum[i - 1][j - (coins[i - 1] * k)]);
                            coinsNum[i][j] = minNums;
                        }else if(value > maxValue){ 
                            maxValue = value;
                            minNums = k + coinsNum[i - 1][j - (coins[i - 1] * k)];
                            coinsNum[i][j] = minNums;
                        }
                    }
                    dp[i][j] = maxValue;
                }
            }
    
            return dp[coins.length][amount] != amount ? -1 : coinsNum[coins.length][amount];
        }
    }

#### [377. 组合总和 Ⅳ][377. _] ####

给定一个由正整数组成且不存在重复数字的数组，找出和为给定目标正整数的组合的个数。

示例:

nums = [1, 2, 3]
    target = 4
    
    所有可能的组合为：
    (1, 1, 1, 1)
    (1, 1, 2)
    (1, 2, 1)
    (1, 3)
    (2, 1, 1)
    (2, 2)
    (3, 1)

请注意，顺序不同的序列被视作不同的组合。

因此输出为 7。

**记忆化搜索**

如果每个节点对任意给定元素都可以选的，不需要给子节点不同标识

class Solution { 
    
        int[] cache;
        public int combinationSum4(int[] nums, int target) { 
            cache = new int[target + 1];
            for(int i = 0 ; i < cache.length ; i ++){ 
                cache[i] = -1;
            }
            return nums.length == 0 ? 0 : dfs(nums , 0 , target);
        }
    
        int dfs(int[] nums, int sumNow , int target){ 
            if(sumNow > target){ 
                return 0;
            }
    
            if(cache[sumNow] != -1){ 
                return cache[sumNow];
            }
            if(sumNow == target){ 
                return 1;
            }
    
            int sum = 0;
            for(int i = 0 ; i < nums.length ; i ++){ 
                sum += dfs(nums , sumNow + nums[i] , target);
            }
    
            cache[sumNow] = sum;
            return sum;
        }
    }

**动态规划**

核心还是找到递推关系

*  可以根据递归时的状态转化图，每个节点决定因素来想

class Solution {
    
        public int combinationSum4(int[] nums, int target) {
           int[] dp = new int[target + 1];
           dp[0] = 1;
           
           for(int i = 1 ; i <= target ; i ++){
               for(int j = 0 ; j < nums.length ; j ++){
                   if(i >= nums[j]){
                       dp[i] += dp[i - nums[j]] ;
                   }
               }
           }
    
           return dp[target];
        }
    }

#### [474. 一和零][474.] ####

给你一个二进制字符串数组 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 。

**记忆化搜索**

如果子节点可选元素受父节点影响

*  对于同一层，并且剩余价值相同的元素来说，其是等价的，可以进行cache和命中
 *  因为同一层就代表了经过了元素个数相同，而剩余的值又相同，就代表上面经过的元素是等价的，所以全部元素里存在完全等价的几部分，那么就没有必要因为等价部分重复相同的动作。

class Solution { 
        int[][][] memo; 
        public int findMaxForm(String[] strs, int m, int n) { 
            boolean[] isUsingIdxBitmap = new boolean[strs.length];
            memo = new int[m + 1][n + 1][strs.length + 1];
            return dfs(strs , m , n , isUsingIdxBitmap , 0);
        }
    
        int dfs(String[] strs , int m , int n , boolean[] isUsingIdxBitmap , int level){ 
            if(level !=0 && memo[m][n][level] != 0){ 
                return memo[m][n][level];
            }
            int max = level;
            for(int i = 0 ; i < isUsingIdxBitmap.length ; i ++){ 
                if(!isUsingIdxBitmap[i]){ 
                    int zeroNum = 0 ,oneNum = 0;
                    for(int j = 0 ; j < strs[i].length() ; j ++){ 
                        char c = strs[i].charAt(j);
                        if(c == '0') zeroNum ++;
                        if(c == '1') oneNum ++;
                    }
                    if(m - zeroNum < 0 || n - oneNum < 0){ 
                        continue;
                    }
    
                    isUsingIdxBitmap[i] = true;
                    max = Math.max(max , dfs(strs , m - zeroNum , n - oneNum , isUsingIdxBitmap , level + 1));
                    isUsingIdxBitmap[i] = false;
                }
            }
    
            memo[m][n][level] = max;
            return max;
        }
    }

**动态规划**

*  **第一步，要明确两点，\[状态\]和\[选择\]。**
    
    状态有三个， \[背包对1的容量\]、\[背包对0的容量\]和 \[可选择的字符串\]；
    
    选择就是对当前遍历到的元素进行何种操作操作（因为任何一个动态规划里，状态一定包含可选字符串，并且肯定会影响使用 dp 数组哪个值，还有如何处理返回值），这道题是把字符串\[装进背包\]或者\[不装进背包\]。
    
    明白了状态和选择，只要往这个框架套就完事儿了：
    
        for 状态1 in 状态1的所有取值：
            for 状态2 in 状态2的所有取值：
                for ...
                    dp[状态1][状态2][...] = 计算(选择1，选择2...)
 *  **第二步，要明确dp数组的定义：**
    
    首先，\[状态\]有三个，所以需要一个三维的dp数组。
    
    `dp[i][j][k]`的定义如下：
    
     *  若只使用前i个物品，当背包容量为j个0，k个1时，能够容纳的最多字符串数。
    
    经过以上的定义，可以得到：
    
     *  `base case为dp[0][..][..] = 0, dp[..][0][0] = 0`。因为如果不使用任何一个字符串，则背包能装的字符串数就为0；如果背包对0，1的容量都为0，它能装的字符串数也为0。
     *  我们最终想得到的答案就是`dp[N][zeroNums][oneNums]`，其中N为字符串的的数量。
 *  **第三步，根据选择，思考状态转移的逻辑：**
    
    注意，这是一个0-1背包问题，每个字符串只有一个选择机会，要么选择装，要么选择不装。
    
     *  如果你不能把这第 i 个物品装入背包（等同于容量不足，装不下去），也就是说你不使用strs\[i\]这一个字符串，那么当前的字符串数`dp[i][j][k]应该等于dp[i - 1][j][k],`继承之前的结果。
     *  如果你可以把这第 i 个物品装入了背包(此时背包容量是充足的，因此要选择装或者不装)，也就是说你能使用 strs\[i\] 这个字符串，那么 `dp[i][j] 应该等于 Max(dp[i - 1][j][k], dp[i - 1][j - zeroNum][k - oneNum] + 1)`。 Max函数里的两个式子，分别是装和不装strs\[i\]的字符串数量。
    
    比如说，如果你想把一个cnt = \[1,2\]的字符串装进背包(在容量足够的前提下)
    
     *  只需要找到容量为`[j - 1][k - 2]`时候的字符串数再加上1，就可以得到装入后的字符串数了。
    
    由于我们求的是最大值，所以我们要求的是装和不装中能容纳的字符串总数更大的那一个。

class Solution { 
        public int findMaxForm(String[] strs, int m, int n) { 
            int[][][] dp = new int[strs.length + 1][m + 1][n + 1];
    
            for(int i = 1 ; i <= strs.length ; i ++){ 
                for(int j = 0 ; j <= m ; j ++){ 
                    for(int k = 0; k <= n ; k ++){ 
                        int zeroNum = 0 , oneNum = 0;
                        for(int cIdx = 0 ; cIdx < strs[i - 1].length() ; cIdx ++){ 
                            if(strs[i - 1].charAt(cIdx) == '0'){ 
                                zeroNum ++ ;
                            } else{ 
                                oneNum ++;
                            }
                        }
                        dp[i][j][k] = j >= zeroNum  && k >= oneNum ? 
                            Math.max(dp[i - 1][j][k] , dp[i - 1][j - zeroNum][k - oneNum] + 1) :
                            dp[i - 1][j][k];
                    }
                }
            }
    
            return dp[strs.length][m][n];
        }
    }

#### [139. 单词拆分][139.] ####

**常规遍历解法**

class Solution { 
        public boolean wordBreak(String s, List<String> wordDict) { 
            List<String> waitWords = new LinkedList<>();
            boolean isNeedAddWord = false;
    
            for(int i = 0 , stackStrIdx = 0 ; i < s.length() ; i ++ , stackStrIdx ++ , isNeedAddWord = false){ 
                isNeedAddWord = waitWords.size() == 0;
    
                for(int j = 0 ; j < waitWords.size() ; ){ 
                    if(waitWords.get(j).length() == stackStrIdx){ 
                        isNeedAddWord = true;
                        waitWords.remove(j);
                    }else if (waitWords.get(j).charAt(stackStrIdx) != s.charAt(i)) { 
                        waitWords.remove(j);
                    }else if (waitWords.get(j).length() - 1 == stackStrIdx && i == s.length() - 1) { 
                        return true;
                    }else{ 
                        j ++;
                    }
                }
    
                if(waitWords.size() !=0 && isNeedAddWord){ 
                    for(int j = 0 ; j < waitWords.size() ; j ++){ 
                        String newS = waitWords.get(0).substring(stackStrIdx);
                        waitWords.remove(0);
                        waitWords.add(newS);
                    }
                }
    
                for(int j = 0 ; isNeedAddWord && j < wordDict.size() ; j ++){ 
                    stackStrIdx = 0;
                    if(s.charAt(i) == wordDict.get(j).charAt(stackStrIdx)){ 
                        if(i == s.length() - 1 && wordDict.get(j).length() == 1){ 
                            return true;
                        }
                        waitWords.add(wordDict.get(j));
                    }
                }
                if(waitWords.size() == 0){ 
                    return false;
                }
            }
    
            return false;
        }
    }

**动态规划**

*  状态：索引（即只需一维数组）
 *  选择：对当前遍历到的元素位置进行哪种操作（即每个节点内部，如何下降到子节点，代表了 dp 数组里中括号的值，与使用该值的条件；还有对子节点返回值进行哪种操作，代表了对 dp 数组返回值作何处理），这里是看 i-str 是否还是单词
 *  编码：对状态进行 for 循环，但是要按照从最后往前的顺序

class Solution {
        public boolean wordBreak(String s, List<String> wordDict) {
            boolean[] dp = new boolean[s.length()];
    
            for(int i = s.length() - 1; i >= 0 ; i --){
                for(String str : wordDict){
                    boolean isMatch = false;
                    for(int j = 0 ; i >= str.length() - 1 && j <= str.length() ; j ++){
                        if(j == str.length()){
                            isMatch = true;
                            break;
                        }
                        if(s.charAt(i - j) != str.charAt(str.length() - 1 - j)){
                            break;
                        }
                    }
    
                    if(isMatch && i == s.length() - 1){
                        dp[i + 1 - str.length()] = true;
                    }else if(isMatch){
                        dp[i + 1 - str.length()] = dp[i + 1 - str.length()] || dp[i + 1];
                    }
                }
            }
    
            return dp[0];
        }
    }

#### [494. 目标和][494.] ####

给定一个非负整数数组，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。

**题解**

核心：

*  状态（决定了 dp 数组的维数，大多都包含可选元素这一属性，如果是每个元素的可以随便使用多次，才不包含可选元素这个属性）
 *  可以转移到哪些状态（决定了使用 dp 数组哪个值，与使用该值的条件，这俩尤其条件一般都跟当前元素有关）
 *  对状态返回值如何处理（即对 dp 数组返回值如何处理）
    
     *  注意：以上两步在正向确定后，就要逆着从递归树的底部开始考虑。
 *  状态决定因素个 for 循环，但是要避免跳跃情况（即例如使用还未遍历到的值，此时就要改变遍历的顺序，把超前的放到最里层，然后初始化好递推的第一排，即 i 和 j 起始位置对应的那一排）

public int findTargetSumWays(int[] nums, int S) { 
            int sum = 0;
            for(int n : nums){ 
                sum += n;
            }
    
            if(S > sum) return 0;
    
            int[][] dp = new int[nums.length + 1][2 * sum + 1];
    	    // 递推要用到的初值提前设定好
            dp[nums.length - 1][sum + nums[nums.length-1]] = dp[nums.length - 1][sum - nums[nums.length-1]] = 
                nums[nums.length-1] != 0 ? 1 : 2;
    
            for(int i = nums.length - 1 ; i >= 0 ; i --){ 
                for(int j = 0 ; j < sum * 2 + 1 ; j ++){ 
                    if(j + nums[i] < sum * 2 + 1){ 
                        dp[i][j] += dp[i + 1][j + nums[i]];
                    }
                    if( j - nums[i] >= 0){ 
                        dp[i][j] += dp[i + 1][j - nums[i]];
                    }
                }
            }
    
            return dp[0][S + sum];
        }
    }

[416.]: https://leetcode-cn.com/problems/partition-equal-subset-sum/
[322.]: https://leetcode-cn.com/problems/coin-change/
[377. _]: https://leetcode-cn.com/problems/combination-sum-iv/
[474.]: https://leetcode-cn.com/problems/ones-and-zeroes/
[139.]: https://leetcode-cn.com/problems/word-break/
[494.]: https://leetcode-cn.com/problems/target-sum/