主要特点以及模板

  • 特点：每个元素只可以使用一次，且大部分都是外循环nums,内循环target,target倒序且target>=nums[i]，但其实外循环target，内循环nums也可以;
  • 按照类型分类主要有三种模板
  1. 最值问题：要求最大值/最小值，此模板的状态转移方程dp[i] = max/min(dp[i], dp[i-nums]+1)或dp[i] = max/min(dp[i], dp[i-num]+nums);
  2. 存在问题(bool)：是否存在…………，满足…………。此模板的状态转移方程dp[i]=dp[i]||dp[i-num];
  3. 组合问题：求所有满足……的排列组合，状态转移方程dp[i]+=dp[i-num];

    416.分割等和子集

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

    示例 1： 输入：nums = [1,5,11,5] 输出：true 解释：数组可以分割成 [1, 5, 5] 和 [11] 。 示例 2： 输入：nums = [1,2,3,5] 输出：false 解释：数组不能分割成两个元素和相等的子集。

    提示： 1 <= nums.length <= 200 1 <= nums[i] <= 100

思路：

  • 如何转化为背包问题：设数组总和sum的一半为背包的容量，这样做是因为分割成等和子集，两个子集的总和是相同的，所以只要让sum的一半作为背包的容量即可。dp最后的结果和sum的一半相等，就可输出true。注意当sum%2不为0时，直接返回false
  • 确定dp[i][j]含义：是指数组中前i个数之和，是否能够达到最大值j ,而i的界限是nums数组长度加1，j的界限是sum/2的值加1 。
  • 确定递推公式： dp[i][j] = Max(dp[i-1][j], num[i]+dp[i-1][j-num[i]])，j>=num[i] dp[i][j] = dp[i-1][j], j<num[i]
  • 初始化：dp[0][j] = num[i] ，j>=num[0]
  • 确定递推顺序 ，二维正序，一维倒序

  • 举列推导dp数组image.png

    1. /**
    2.    * 二维数组dp
    3.    * @param nums
    4.    * @return
    5.    */
    6.   public static boolean canPartition(int[] nums) {
    7.       //可以把其看作01背包问题
    8.       //sum/2是背包的最大重量
    9.       int sum = 0;
    10.       for (int i = 0; i < nums.length; i++) {
    11.           sum += nums[i];
    12.       }
    13.       //如果sum是奇数，则不可能分割为等和子集
    14.       if (sum % 2 == 1) {
    15.           return false;
    16.       }
    17.       sum = sum / 2;
    18.       int len = nums.length;
    19.       int[][] dp = new int[len][sum + 1];
    20.       for (int i = 1; i < sum + 1; i++) {
    21.           if (nums[0] <= i) {
    22.               dp[0][i] = nums[0];
    23.           }
    24.       }
    25.       for (int i = 1; i < len; i++) {
    26.           for (int j = 1; j < sum + 1; j++) {
    27.               if (nums[i] <= j) {
    28.                   int v1 = nums[i] + dp[i - 1][j - nums[i]];
    29.                   int v2 = dp[i - 1][j];
    30.                   dp[i][j] = Math.max(v1, v2);
    31.               } else dp[i][j] = dp[i - 1][j];
    33.           }
    34.       }
    35.       return dp[len - 1][sum] == sum;
    36.   }

    一维数组的dp思路也是类似的，只是在确定递推顺序有不同，一维数组中递推顺序应该从后面往前递推

    1. /**
    2.    * 一维数组dp
    3.    * @param nums
    4.    * @return
    5.    */
    6.   public static boolean canPartition2(int[] nums) {
    7.       int sum = 0;
    8.       for (int i = 0; i < nums.length; i++) {
    9.           sum += nums[i];
    10.       }
    11.       //如果sum是奇数，则不可能分割为等和子集
    12.       if (sum % 2 == 1) {
    13.           return false;
    14.       }
    15.       sum = sum / 2;
    16.       int len = nums.length;
    17.       int[] dp = new int[sum + 1];
    18.       for (int i = 0; i < sum + 1; i++) {
    19.           if (i >= nums[0]) {
    20.               dp[i] = nums[0];
    21.           }
    22.       }
    23.       for (int i = 1; i < len; i++) {
    24.           //递推顺序从后往前
    25.           for (int j = sum; j >= 0; j--) {
    26.               if (j >= nums[i]) {
    27.                   dp[j] = Math.max(dp[j], nums[i] + dp[j - nums[i]]);
    28.               }
    29.           }
    30.       }
    31.       return dp[sum] == sum;
    32.   }

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

    有一堆石头，用整数数组 stones 表示。其中 stones[i] 表示第 i 块石头的重量。

    每一回合，从中选出任意两块石头，然后将它们一起粉碎。假设石头的重量分别为 x 和 y，且 x <= y。那么粉碎的可能结果如下： 如果 x == y，那么两块石头都会被完全粉碎； 如果 x != y，那么重量为 x 的石头将会完全粉碎，而重量为 y 的石头新重量为 y-x。 最后，最多只会剩下一块 石头。返回此石头 最小的可能重量 。如果没有石头剩下，就返回 0。

    示例 1： 输入：stones = [2,7,4,1,8,1] 输出：1 解释： 组合 2 和 4，得到 2，所以数组转化为 [2,7,1,8,1]， 组合 7 和 8，得到 1，所以数组转化为 [2,1,1,1]， 组合 2 和 1，得到 1，所以数组转化为 [1,1,1]， 组合 1 和 1，得到 0，所以数组转化为 [1]，这就是最优值。

    示例 2： 输入：stones = [31,26,33,21,40] 输出：5

    提示： 1 <= stones.length <= 30 1 <= stones[i] <= 100

  • 思路：

  • 如何转化成01背包问题？先把这个问题转化为把全部石头分成两堆石头，然后求两堆石头重量差的最小值。可以得出要求出最小值，就要让两堆石头重量都近似等于sum/2。即只要有一堆石头的值近似等于，另一堆也会近似等于。所以就可以容易将上述问题转化成背包问题，背包容量为sum/2,每次要把石头的重量放进背包中，可放进去的那一堆石头最大重量为maxWeight，所以另一堆石头的重量为sum-maxWeight，所以两堆石头的最小可能重量为（sum-maxWeight）-maxWeight 的绝对值，即sum-2*maxWeight的绝对值。
  • 为了好理解，下面都是用二维dp的形式来讲解思路，而实现代码则直接用一维dp
  • 确定dp含义：dp[i][j] 是指前 i 块石头在背包容量为 j 下能达到的最大重量之和。
  • 确定递推公式：由于转化为01背包问题，所以易得 dp[i][j] = max(dp[i-1][j], num[i] + dp[i-1][j-num[i]]) , j>=num[i] dp[i][j] = dp[i-1][j] , j < num[i]
  • 初始化dp ： dp[0][j] = num[0] , j >=num[0]
  • 确定递推顺序：二维正序，一维倒序
  • 举例推导dpimage.png
    1.   /**
    2.    * 可以使这道问题转化为背包问题，可以这样想：
    3.    *      把这一堆石头分成两堆，并使这两堆石头重量之差的绝对值最小
    4.    *      这就和416思路相似
    5.    * 思路：先求出sum/2,然后dp表按照sum/2的长度打表，
    6.    * @param stones
    7.    * @return
    8.    */
    9.   public static int lastStoneWeightII(int[] stones) {
    10.       int len = stones.length;
    11.       int sum = 0;
    12.       for (int stone : stones) {
    13.           sum += stone;
    14.       }
    15.       //背包重量
    16.       int bagWeight = sum / 2;
    17.       int[] dp = new int[bagWeight + 1];
    18.       for (int i = 0; i < bagWeight + 1; i++) {
    19.           if (i >= stones[0]) {
    20.               dp[i] = stones[0];
    21.           }
    22.       }
    23.       for (int i = 1; i < len; i++) {
    24.           int temp = stones[i];
    25.           for (int j = bagWeight; j >=0 ; j--) {
    26.               if (j >= temp) {
    27.                   dp[j] = Math.max(dp[j], dp[j - temp] + temp);
    28.               }
    29.           }
    30.       }
    31.       //即(sum - dp[bagWeight]) - dp[bagWeight] 的绝对值
    32.       return Math.abs(sum - dp[bagWeight] - dp[bagWeight]);
    33.   }

    494.目标和

    给你一个整数数组 nums 和一个整数 target 。 向数组中的每个整数前添加 ‘+’ 或 ‘-‘ ，然后串联起所有整数，可以构造一个 表达式 ： 例如，nums = [2, 1] ，可以在 2 之前添加 ‘+’ ，在 1 之前添加 ‘-‘ ，然后串联起来得到表达式 “+2-1” 。 返回可以通过上述方法构造的、运算结果等于 target 的不同 表达式 的数目。

    示例 1： 输入：nums = [1,1,1,1,1], target = 3 输出：5 解释：一共有 5 种方法让最终目标和为 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 +1 + 1 + 1 + 1 - 1 = 3

    示例 2： 输入：nums = [1], target = 1 输出：1

    提示： 1 <= nums.length <= 20 0 <= nums[i] <= 1000 0 <= sum(nums[i]) <= 1000 -1000 <= target <= 1000

解法1：回溯

  • 思路：背包问题的暴力解法就是用回溯来解决。这一题的回溯不是选与不选数组中的数，而是在选择加上或者是减去这个数。要实现这个思路，则只需要用两个递归就可解决。递归1选择加上这个数，递归2选择减去这个数。

    1. static int ans;
    2.   public static int findTargetSumWays(int[] nums, int target) {
    3.       ans = 0;
    4.       int sum = 0;
    5.       dfs(nums, target,0,sum);
    6.       return ans;
    7.   }
    9.   private static void dfs(int[] nums, int target,int current,int sum) {
    10.       int len = nums.length;
    11.       if (current == len) {
    12.           if (sum == target) {
    13.               ans++;
    14.           }
    15.           return;
    16.       }
    17.       //加上这个数
    18.       dfs(nums, target, current + 1, sum + nums[current]);
    19.       //减去这个数
    20.       dfs(nums, target, current + 1, sum - nums[current]);
    21.   }

    解法2：dp

  • 思路：

  • 如何转化成01背包问题？把全部数分成两堆，一堆是要被减去的数，一堆是要加上的数 ，设要被减去的数的和为neg，全部数的总和为sum，则要要加上的数为sum-neg，则要加上的数之和减去要减的数之和的结果为题目要求的数target，则（sum-neg）-neg = target，可以求得neg = （sum - target）/2 。让背包最大容量为neg，则dp[nums.length][neg] 为要求target时要被减去的数一共能够取到最大的方法数。
  • 确定dp含义：dp[i][j]代表选取前i个数在背包容量 j 即选取前i个数的元素加到 j 一共有多少种方法数
  • 确定递推公式：dp[i][j] = dp[i-1][j - num[i]] + dp[i-1][j] , j>=nums[i] dp[i][j] = dp[i-1][j] , j<=nums[i]
  • 初始化dp，i的范围是0<=i<=nums.length,所以dp[0][0]表示不选任何元素的情况下能够组成0，所以dp[0][0] = 1, 且当 i= 0,j>0时dp[0][j] = 0
  • 确定递推顺序

  • 举例推导dp

    1.   ![image.png](https://cdn.nlark.com/yuque/0/2022/png/27659252/1650723637314-8559dcf3-89c3-47ce-a167-2a8c9800f6bd.png#clientId=ubb497e00-fdcd-4&crop=0&crop=0&crop=1&crop=1&from=paste&height=222&id=u8a28d487&margin=%5Bobject%20Object%5D&name=image.png&originHeight=277&originWidth=740&originalType=binary&ratio=1&rotation=0&showTitle=false&size=10144&status=done&style=none&taskId=uc911500f-3aee-42af-9be0-a4809e3f37e&title=&width=592)
    1. public static int findTargetSumWays2(int[] nums, int target) {
    2.       //设sum是数组总和，neg是要减去数的总和，可得（sum-neg）-neg = target
    3.       //即neg = （sum-target）/ 2
    4.       int sum = 0;
    5.       for (int num : nums) {
    6.           sum += num;
    7.       }
    8.       int diff = sum - target;
    9.       if (diff < 0 || diff % 2 != 0) {
    10.           return 0;
    11.       }
    12.       int neg = diff / 2;
    13.       //dp[i]指的是当前前j个数能组成neg的方法数
    14.       int[] dp = new int[neg + 1];
    15.       dp[0] = 1;
    16.       for (int num : nums) {
    17.           for (int j = neg; j >= 0; j--) {
    18.               if (j >= num) {
    19.                   dp[j] = dp[j] + dp[j - num];
    20.               }
    21.           }
    22.       }
    23.       return dp[neg];
    24.   }

    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 。

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

  • 思路：

  • 如何转化为背包问题？这题和经典的01背包问题很像，01背包只有一个背包容量，而这题可以看成有两个背包容量，两个背包分别装的是0或者1 。所以这题要用二维背包来做。对每个物品，都是选与不选，且只有当背包容量足够的情况下，才对这个物品进行选与不选的讨论。
  • 确定dp含义：dp[i][j][k] 分别指的是在最多j个0和最多k个1的背包最大子集的长度。
  • 确定递推公式：dp[i][j][k] = dp[i-1][j - 当前元素0的个数][k - 当前元素1的个数] + 1 ，选择当前元素 dp[i][j][k] = dp[i-1][j][k] ,不选择当前元素
  • 初始化dp ： 简便计算，让第一行不代表任何元素，所以第一行dp[0][j][k] = 0
  • 确定递推顺序

  • 举例推导dp

    1.   public static int findMaxForm(String[] strs, int m, int n) {
    2.       int len = strs.length;
    3.       int[][][] dp = new int[len + 1][m + 1][n + 1];
    4.       for (int i = 1; i <= len; i++) {
    5.           int[] count = getCount(strs[i - 1]);
    6.           int zeros = count[0];
    7.           int ones = count[1];
    8.           for (int j = 0; j <= m; j++) {
    9.               for (int k = 0; k <= n; k++) {
    10.                   dp[i][j][k] = dp[i - 1][j][k];
    11.                   if (j >= zeros && k >= ones) {
    12.                       dp[i][j][k] = Math.max(dp[i][j][k], dp[i - 1][j - zeros][k - ones] + 1);
    13.                   }
    14.               }
    15.           }
    16.       }
    17.       return dp[len][m][n];
    18.   }
    20.   //这是找出当前0和1元素个数的方法
    21.   public static int[] getCount(String str) {
    22.       int[] count = new int[2];
    23.       for (char c : str.toCharArray()) {
    24.           count[c - '0']++;
    25.       }
    26.       return count;
    27.   }
    1.   public static int findMaxForm2(String[] strs, int m, int n) {
    2.       int[][] dp = new int[m + 1][n + 1];
    3.       for (String str : strs) {
    4.           int[] count = getCount(str);
    5.           int zeros = count[0];
    6.           int ones = count[1];
    7.           for (int j = m; j >= zeros; j--) {
    8.               for (int k = n; k >= ones; k--) {
    9.                   dp[j][k] = Math.max(dp[j][k], dp[j - zeros][k - ones] + 1);
    10.               }
    11.           }
    12.       }
    13.       return dp[m][n];
    14.   }
    16.   //这是找出当前0和1元素个数的方法
    17.   public static int[] getCount(String str) {
    18.       int[] count = new int[2];
    19.       for (char c : str.toCharArray()) {
    20.           count[c - '0']++;
    21.       }
    22.       return count;
    23.   }