1. 背包问题

139. 单词拆分

给定一个非空字符串 s 和一个包含非空单词列表的字典 wordDict，判定 s 是否可以被空格拆分为一个或多个在字典中出现的单词。

说明：
拆分时可以重复使用字典中的单词。
你可以假设字典中没有重复的单词。

377. 组合总和 Ⅳ

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

2. 0-1背包问题

作为“0-1 背包问题”，它的特点是：“每个数只能用一次”。思路是：物品一个一个选，容量也一点一点放大考虑（这一点是“动态规划”的思想，特别重要）。如果在实际生活中，其实我们也是这样做的，一个一个尝试把候选物品放入“背包”，看什么时候能容纳的价值最大。

具体做法是：画一个 len 行，target + 1 列的表格。这里 len 是物品的个数，target 是背包的容量。len 行表示一个一个物品考虑，target + 1多出来的那 1 列，表示背包容量从 0 开始，很多时候，我们需要考虑这个容量为 0 的数值。

416. 分割等和子集

给定一个只包含正整数的非空数组。是否可以将这个数组分割成两个子集，使得两个子集的元素和相等。
注意:
每个数组中的元素不会超过 100
数组的大小不会超过 200

思路：
做这道题需要做这样一个等价转换：是否可以从这个数组中挑选出一些正整数，使得这些数的和等于整个数组元素的和的一半。前提条件是：数组的和一定得是偶数，即数组的和一定得被 22 整除，这一点是特判。

状态定义：dp[i][j]表示从数组的 [0, i] 这个子区间内挑选一些正整数，每个数只能用一次，使得这些数的和恰好等于 j。
状态转移方程：很多时候，状态转移方程思考的角度是“分类讨论”，对于“0-1 背包问题”而言就是“当前考虑到的数字选与不选”。
1、不选择 nums[i]，如果在 [0, i - 1] 这个子区间内已经有一部分元素，使得它们的和为 j ，那么 dp[i][j] = true；

2、选择 nums[i]，如果在 [0, i - 1] 这个子区间内就得找到一部分元素，使得它们的和为 j - nums[i]。

状态转移方程是：
dp[i][j] = dp[i - 1][j] or dp[i - 1][j - nums[i]]
一般写出状态转移方程以后，就需要考虑边界条件（一般而言也是初始化条件）。

方法一：动态规划

  1. class Solution {
  2.     public boolean canPartition(int[] nums) {
  3.         int len = nums.length;
  4.         int sum = 0;
  5.         for (int i = 0; i < len; i++) {
  6.             sum += nums[i];
  7.         }
  8.         if ((sum&1) == 1) return false;
  9.         int target = sum >> 1;
  10.         // 状态定义：dp[i][j]表示从数组的 [0, i] 这个子区间内挑选一些正整数，每个数只能用一次，使得这些数的和恰好等于 j
  11.         boolean[][] dp = new boolean[len][target+1];
  12.         if (nums[0] <= target) {
  13.             dp[0][nums[0]] = true;
  14.         }
  15.         for (int i = 1; i < len; i++) {
  16.             for (int j = 0; j <= target; j++) {
  17.                 // 直接从上一行先把结果抄下来，然后再修正
  18.                 dp[i][j] = dp[i - 1][j];
  20.                 if (nums[i] == j) {
  21.                     dp[i][j] = true;
  22.                     continue;
  23.                 }
  24.                 if (nums[i] < j) {
  25.                     dp[i][j] = dp[i - 1][j] || dp[i - 1][j - nums[i]];
  26.                 }
  27.             }
  28.         }
  30.         return dp[len - 1][target];
  31.     }
  32. }

方法二：动态规划-优化1，提前结束

  1. class Solution {
  2.     public boolean canPartition(int[] nums) {
  3.         int len = nums.length;
  4.         int sum = 0;
  5.         for (int i = 0; i < len; i++) {
  6.             sum += nums[i];
  7.         }
  8.         if ((sum&1) == 1) return false;
  9.         int target = sum >> 1;
  10.         // 状态定义：dp[i][j]表示从数组的 [0, i] 这个子区间内挑选一些正整数，每个数只能用一次，使得这些数的和恰好等于 j
  11.         boolean[][] dp = new boolean[len][target+1];
  12.         if (nums[0] <= target) {
  13.             dp[0][nums[0]] = true;
  14.         }
  15.         for (int i = 1; i < len; i++) {
  16.             for (int j = 0; j <= target; j++) {
  17.                 // 直接从上一行先把结果抄下来，然后再修正
  18.                 // dp[i][j] = dp[i - 1][j];
  20.                 if (nums[i] == j) {
  21.                     dp[i][j] = true;
  22.                     continue;
  23.                 }
  24.                 if (nums[i] < j) {
  25.                     dp[i][j] = dp[i - 1][j] || dp[i - 1][j - nums[i]];
  26.                 }
  27.             }
  29.             // 优化1：由于状态转移方程的特殊性，提前结束，可以认为是剪枝操作
  30.             if (dp[i][target]) {
  31.                 return true;
  32.             }
  33.         }
  35.         return dp[len - 1][target];
  36.     }
  37. }

方法三：动态规划-优化2，一维dp数组
“0-1 背包问题”常规优化：“状态数组”从二维降到一维，减少空间复杂度。

在“填表格”的时候，当前行只参考了上一行的值，因此状态数组可以只设置 22 行，使用“滚动数组”的技巧“填表格”即可；

实际上连“滚动数组”都不必，在“填表格”的时候，当前行总是参考了它上面一行 “头顶上” 那个位置和“左上角”某个位置的值。因此，我们可以只开一个一维数组，从后向前依次填表即可。

这一点第 1 次接触的时候，可能会觉得很奇怪，理解的办法是，就拿题目中的示例，画一个表格，自己模拟一遍程序是如何“填表”的行为，就很清楚为什么状态数组压缩到 1 行的时候，需要“从后前向”填表。

“从后向前” 写的过程中，一旦 nums[i] <= j 不满足，可以马上退出当前循环，因为后面的 j 的值肯定越来越小，没有必要继续做判断，直接进入外层循环的下一层。相当于也是一个剪枝，这一点是“从前向后”填表所不具备的。

public class Solution {

    public boolean canPartition(int[] nums) {
        int len = nums.length;
        if (len == 0) {
            return false;
        }

        int sum = 0;
        for (int num : nums) {
            sum += num;
        }

        if ((sum & 1) == 1) {
            return false;
        }

        int target = sum / 2;

        boolean[] dp = new boolean[target + 1];
        dp[0] = true;

        if (nums[0] <= target) {
            dp[nums[0]] = true;
        }

        for (int i = 1; i < len; i++) {
            for (int j = target; nums[i] <= j; j--) {
                if (dp[target]) {
                    return true;
                }

                dp[j] = dp[j] || dp[j - nums[i]];
            }
        }
        return dp[target];
    }
}

方法四：暴力搜索
回溯出所有情况，超时。

class Solution {
    private boolean flag = false;
    public boolean canPartition(int[] nums) {
        int len = nums.length;
        int sum = 0;
        for (int i = 0; i < len; i++) {
            sum += nums[i];
        }
        if ((sum&1) == 1) return false;
        int target = sum >> 1;

        helper(new ArrayList<>(), 0, nums, target);
        return flag;
    }

    private void helper(List<Integer> list, int index, int[] nums, int target) {
        if (sum(list) == target) {
            flag = true;
        }
        for (int n : list) {
            System.out.print(n+ " ");
        }
        System.out.println();        
        for (int i = index; i < nums.length; i++) {
            list.add(nums[i]);
            helper(list, i + 1, nums, target);
            list.remove(list.size() - 1);
            if (flag == true) {
                return;
            }
        }
    }

    private int sum(List<Integer> list) {
        int sum = 0;
        for (int a : list) {
            sum += a;
        }
        return sum;
    }
}

474. 一和零

在计算机界中，我们总是追求用有限的资源获取最大的收益。
现在，假设你分别支配着 m 个 0 和 n 个 1。另外，还有一个仅包含 0 和 1 字符串的数组。
你的任务是使用给定的 m 个 0 和 n 个 1 ，找到能拼出存在于数组中的字符串的最大数量。每个 0 和 1 至多被使用一次。

注意:
给定 0 和 1 的数量都不会超过 100。
给定字符串数组的长度不会超过 600。

494. 目标和

给定一个非负整数数组，a1, a2, …, an, 和一个目标数，S。现在你有两个符号 + 和 -。对于数组中的任意一个整数，你都可以从 + 或 -中选择一个符号添加在前面。
返回可以使最终数组和为目标数 S 的所有添加符号的方法数。

3. 完全背包问题

完全背包问题：LeetCode 322、518