LeetCode题解 - 动态规划-背包问题

谁借莪１个温暖的怀抱￠ 2023-01-17 10:41 214阅读 0赞

# LeetCode题解 - 动态规划-背包问题 #

### 文章目录 ###

*  LeetCode题解 - 动态规划-背包问题
 *   *  0-1背包
     *   *  416. 分割等和子集（中等）
         *  494. 目标和（中等）
         *  474. 一和零（中等）
     *  完全背包问题
     *   *  518. 零钱兑换 II （中等）
         *  322. 零钱兑换（中等）
         *  139. 单词拆分（中等）
         *  377. 组合总和 IV（中等）

--------------------

讲解部分参考：作者：labuladong 公众号：labuladong

## 0-1背包 ##

给你一个可装载重量为`W`的背包和`N`个物品，每个物品有重量和价值两个属性。其中第`i`个物品的重量为`wt[i]`，价值为`val[i]`，现在让你用这个背包装物品，最多能装的价值是多少？**这个题目中的物品不可以分割，要么装进包里，要么不装，不能说切成两块装一半。**

举个简单的例子，输入如下：

N = 3, W = 4
    wt = [2, 1, 3]
    val = [4, 2, 3]
    算法返回 6，选择前两件物品装进背包，总重量 3 小于`W`，可以获得最大价值 6。

1.**明确两点，「状态」和「选择」**： 状态有两个，就是「背包的容量」和「可选择的物品」。选择就是「装进背包」或者「不装进背包」嘛。

明白了状态和选择，动态规划问题基本上就解决了，只要往这个框架套就完事儿了：

for 状态1 in 状态1的所有取值：
        for 状态2 in 状态2的所有取值：
            for ...
                dp[状态1][状态2][...] = 择优(选择1，选择2...)

1.  **明确`dp`数组的定义**:
    
    首先看看刚才找到的「状态」，有两个，也就是说我们需要一个二维`dp`数组，一维表示可选择的物品，一维表示背包的容量。
    
    **`dp[i][w]`的定义如下：对于前`i`个物品，当前背包的容量为`w`，这种情况下可以装的最大价值是`dp[i][w]`。**
    
    比如说，如果 `dp[3][5]` = 6，其含义为：对于给定的一系列物品中，若只对前 3 个物品进行选择，当背包容量为 5 时，最多可以装下的价值为 6。

根据这个定义，**我们想求的最终答案就是`dp[N][W]`。base case 就是`dp[0][..] = dp[..][0] = 0`**，因为没有物品或者背包没有空间的时候，能装的最大价值就是 0。

细化上面的框架：

nt dp[N+1][W+1]
    dp[0][..] = 0
    dp[..][0] = 0
    for i in [1..N]:
        for w in [1..W]:
            dp[i][w] = max(
                把物品 i 装进背包,
                不把物品 i 装进背包
            )
    return dp[N][W]

1.  **根据「选择」，思考状态转移的逻辑**。
    
    (1) 如果你没有把这第`i`个物品装入背包，那么很显然，最大价值`dp[i][w]`应该等于`dp[i-1][w]`。你不装嘛，那就继承之前的结果。
    
    (2) 如果你把这第`i`个物品装入了背包，那么`dp[i][w]`应该等于`dp[i-1][w-wt[i-1]] + val[i-1]`。(剩余重量`w-wt[i-1]`限制下能装的最大价值，加上第`i`个物品的价值`val[i-1]`)
    
    由于`i`是从 1 开始的，所以对`val`和`wt`的取值是`i-1`。

for i in [1..N]:
        for w in [1..W]:
            dp[i][w] = max(
                dp[i-1][w],
                dp[i-1][w - wt[i-1]] + val[i-1]
            )
    return dp[N][W]

**最后一步**，把伪码翻译成代码，处理一些边界情况。

public int knapsack(int W, int N, int[] weights, int[] values) {
        
        int[][] dp = new int[N + 1][W + 1];
        for (int i = 1; i <= N; i++) {
        
            for (int w = 1; w <= W; j++) {
        
                if (w - weights[i-1] < 0) {
        
                    // 当前背包容量装不下，只能选择不装入背包
                    dp[i][w] = dp[i - 1][w];
                } else {
        
                    // 装入或者不装入背包，择优
                    dp[i][w] = max(dp[i - 1][w - weights[i-1]] + values[i-1], 
                                   dp[i - 1][w]);
                }
            }
        }
        return dp[N][W];
    }

**4. 空间优化**

在程序实现时可以对 0-1 背包做优化。观察状态转移方程可以知道，前 i 件物品的状态仅与前 i-1 件物品的状态有关，因此可以将 dp 定义为一维数组，其中 dp\[j\] 既可以表示 `dp[i-1][j]` 也可以表示 `dp[i][j]`。此时 `dp[j] = max(dp[j], dp[j - w] + v)`

在该式中 `dp[j-w]` 表示 `dp[i-1][j-w]`，即在计算`dp[i][j]`时会需要用到`i-1`时的数据，因此如果 j 从小到大遍历，会先求 `dp[i][j-w]`，从而会导致 `dp[i-1][j-w]`被覆盖，使得计算`dp[i][j]`时出现错误

也就是说为防止覆盖，要先计算 `dp[i][j]`再计算 `dp[i][j-w]`，在程序实现时需要按倒序来循环求解。

public int knapsack(int W, int N, int[] weights, int[] values) {
        
        int[] dp = new int[W + 1];
        for (int i = 1; i <= N; i++) {
        
            int w = weights[i - 1], v = values[i - 1];
            for (int j = W; j >= 1; j--) {
        
                if (j >= w) {
        
                    dp[j] = Math.max(dp[j], dp[j - w] + v);
                }
            }
        }
        return dp[W];
    }

--------------------

### 416. 分割等和子集（中等） ###

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

输入：nums = [1,5,11,5]
    输出：true
    解释：数组可以分割成 [1, 5, 5] 和 [11] 。

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

**解题思路**：本题与 0-1 背包问题有一个很大的不同，即：

*  0-1 背包问题选取的物品的容积总量**不能超过**规定的总量；
 *  本题选取的数字之和需要**恰好等于**规定的和的一半。

这一点区别，决定了在初始化的时候，所有的值应该初始化为 false。

1.  状态定义：`dp[i][j]`表示从数组的 `[0, i]` 这个子区间内挑选一些正整数，每个数只能用一次，使得这些数的和**恰好等于** `j`
2.  状态转移方程：很多时候，状态转移方程思考的角度是「分类讨论」，对于「0-1 背包问题」而言就是「当前考虑到的数字选与不选」。

*  当`nums[i] <= j`时，如果不选择 `nums[i]`，那么 `dp[i][j] = dp[i - 1][j]`；如果选择 `nums[i]`，如果在 `[0, i - 1]` 这个子区间内就得找到一部分元素，使得它们的和为 `j - nums[i]`，即 `dp[i][j] = dp[i - 1][j] | dp[i - 1][j - nums[i]]`；
 *  当`nums[i] <= j`时，无法选择 `nums[i]`，那么 `dp[i][j] = dp[i - 1][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;
            int target = sum / 2;
            boolean[][] dp = new boolean[n + 1][target + 1];
            dp[0][0] = true; //base case, 其余都为false
            for(int i = 1; i <= n; i++){
        
                int num = nums[i - 1];
                for(int j = 1; j <= target; 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[n][target];
        }
    }

**空间优化**

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;
            int target = sum / 2;
            boolean[] dp = new boolean[target + 1];
            dp[0] = true; //base case, 其余都为false
            for(int num : nums){
        
                for(int j = target; j >= num; j--){
        
                    dp[j] = dp[j] || dp[j - num]; //||和|都是表示“或”，区别是||只满足第一个条件，后面条件就不再判断，而|要对所有的条件进行判断。
                }
            }
            return dp[target];
        }
    }

--------------------

### 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。

**解题思路**：01背包问题是选或者不选，但本题是必须选，是选+还是选-。先将本问题转换为01背包问题。

**方法一（二维数组）**：[参考链接][Link 1]

在**背包载重最大为j的情况下，对前i个物品进行选择**。状态转移方程：`dp[i][j] = dp[i-1][j+nums[i]] + dp[i-1][j-nums[i]]`

**解释**：`j+nums[i]`和`j-nums[i]`表示对nums\[i\]执行减，或者执行加，那么`dp[i][j]`的结果值就是加/减之后对应位置的和。

接下来需要明确base case，因为整个状态的范围长度`length = sum*2 + 1`，而j是从0开始的，故其初始化的位置应为sum。故dp表初始化应为：

if(nums[0] == 0) dp[0][sum] = 2;//如果nums[0]==0的话，那么+0和-0都应该算作其操作，故if(nums[0] == 0) dp[0][sum] = 2;
    else{
        
        dp[0][sum+nums[0]] = 1;
        dp[0][sum-nums[0]] = 1;
    }

lass Solution{
        
        public int findTargetSumWays(int[] nums, int S){
        
            if(nums.length == 0) return 0;
            int sum = 0;
            for(int i = 0; i < nums.length; i++) sum += nums[i];
            if (Math.abs(S) > Math.abs(sum)) return 0;
            int[][] dp = new int[nums.length][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<nums.length; i++){
        
                for(int j = 0; j<(sum*2+1);j++){
        
                    int l = (j - nums[i]) >= 0 ? j - nums[i] : 0;
                    int r = (j + nums[i]) < (sum*2+1) ? j + nums[i] : 0;
                    dp[i][j] = dp[i-1][l] + dp[i-1][r];
                }
            }
            return dp[nums.length-1][sum+S];
        }
    }

**方法二（状态优化：一维数组）**：[参考链接][Link 2]

1.  假设所有符号为+的元素和为x，符号为-的元素和的绝对值是y。我们想要的 S = 正数和 - 负数和 = x - y，而已知x与y的和是数组总和：x + y = sum  
    可以求出x = (S + sum) / 2 = target，也就是我们要从nums数组里选出几个数，令其和为target
    
    于是就转化成了**求容量为target的01背包问题 =>要装满容量为target的背包，有几种方案**
2.  特例判断  
    如果S大于sum，不可能实现，返回0  
    如果x不是整数，也就是S + sum不是偶数，不可能实现，返回0
3.  dp\[j\]代表的意义：填满容量为j的背包，有dp\[j\]种方法。因为填满容量为0的背包有且只有一种方法，所以dp\[0\] = 1
4.  状态转移：dp\[j\] = dp\[j\] + dp\[j - num\]，  
    当前填满容量为j的包的方法数 = 之前填满容量为j的包的方法数 + 之前填满容量为j - num的包的方法数  
    也就是当前数num的加入，可以把之前和为j - num的方法数加入进来。

class Solution {
        
        public int findTargetSumWays(int[] nums, int S) {
        
            int sum = 0;
            for(int num : nums){
        
                sum += num;
            }
            if(sum < S || (sum + S) % 2 != 0) return 0; 
            int target = (sum + S)/2;
            int[] dp = new int[target + 1];
            dp[0] = 1;
            for(int num : nums){
        
                for(int j = target; j >= num; j--){
        
                    dp[j] = dp[j] + dp[j - num];
                }
            }
            return dp[target];
        }
    }

--------------------

### 474. 一和零（中等） ###

给你一个二进制字符串数组 `strs` 和两个整数 `m` 和 `n` 。请你找出并返回 `strs` 的最大子集的大小，该子集中 **最多** 有 `m` 个 `0` 和 `n` 个 `1` ，如果 `x` 的所有元素也是 `y` 的元素，集合 `x` 是集合 `y` 的 **子集** 。

输入：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 。

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

**解题思路**：把总共的 0 和 1 的个数视为背包的容量，每一个字符串视为装进背包的物品。这道题就可以使用 0-1 背包问题的思路完成，这里的目标值是能放进背包的字符串的数量。

1.  **定义状态**：尝试题目问啥，就把啥定义成状态。`dp[i][j][k]` 表示输入字符串在子区间 \[0, i\] 能够使用 j 个 0 和 k 个 1 的字符串的最大数量。
2.  **状态转移方程**：`dp[i][j][k]= Math.max(dp[i-1][j][k], dp[i-1][j-zeroNum][k-oneNum])`
3.  **初始化**：为了避免分类讨论，通常多设置一行。这里可以认为，第 0 个字符串是空串。第 00行默认初始化为 0。
4.  **输出**：输出是最后一个状态，即：`dp[len][m][n]`
5.  **第 5 步：思考优化空间**
    
    因为当前行只参考了上一行的值，因此可以「从后向前赋值」。

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

--------------------

## 完全背包问题 ##

### 518. 零钱兑换 II （中等） ###

给定不同面额的硬币和一个总金额。写出函数来计算可以凑成总金额的硬币组合数。**假设每一种面额的硬币有无限个**。

输入: amount = 5, coins = [1, 2, 5]
    输出: 4
    解释: 有四种方式可以凑成总金额:
    5=5
    5=2+2+1
    5=2+1+1+1
    5=1+1+1+1+1

**解题思路**：**我们可以把这个问题转化为背包问题的描述形式**：

有一个背包，最大容量为`amount`，有一系列物品`coins`，每个物品的重量为`coins[i]`，**每个物品的数量无限**。请问有多少种方法，能够把背包恰好装满？

这个问题和我们前面讲过的两个背包问题，有一个最大的区别就是，每个物品的数量是无限的，这也就是传说中的「**完全背包问题**」，没啥高大上的，无非就是状态转移方程有一点变化而已。

**1. 明确两点，「状态」和「选择」**：状态有两个，就是「背包的容量」和「可选择的物品」，选择就是「装进背包」或者「不装进背包」。

**2. 第二步要明确`dp`数组的定义**：`dp[i][j]`的定义如下：**若只使用前`i`个物品，当背包容量为`j`时，有`dp[i][j]`种方法可以装满背包。**

换句话说，翻译回我们题目的意思就是：**若只使用`coins`中的前`i`个硬币的面值，若想凑出金额`j`，有`dp[i][j]`种凑法**。

**3. base case**： 为`dp[0][..] = 0， dp[..][0] = 1`。因为如果不使用任何硬币面值，就无法凑出任何金额；如果凑出的目标金额为 0，那么“无为而治”就是唯一的一种凑法。我们最终想得到的答案就是`dp[N][amount]`，其中`N`为`coins`数组的大小。

**4.根据「选择」，思考状态转移的逻辑**：

*  **如果你不把这第`i`个物品装入背包**，也就是说你不使用`coins[i]`这个面值的硬币，那么凑出面额`j`的方法数`dp[i][j]`应该等于`dp[i-1][j]`，继承之前的结果。
 *  **如果你把这第`i`个物品装入了背包**，也就是说你使用`coins[i]`这个面值的硬币，那么==`dp[i][j]`应该等于`dp[i][j-coins[i-1]]`==。
    
    （为什么会这样，这就是01背包和完全背包的区别，也是状态压缩后为啥01背包内部循环需要倒序而完全背包不需要。 就因为01背包元素的唯一的，完全背包元素是无限制的。使用dp\[i - 1\]代表不会关联到当前元素所以不重复，使用dp\[i\]会关联到当前元素所以支持重复选择。）

二维数组代码：

class Solution {
        
        public int change(int amount, int[] coins) {
        
            int n = coins.length;
            int[][] dp = new int[n + 1][amount + 1];
            for(int i = 0; i <= n; i++){
        
                dp[i][0] = 1;
            }
            for(int i = 1; i <= n; i++){
        
                for(int j = 1; j <= amount; j++){
        
                    if(j >= coins[i - 1]){
        
                        dp[i][j] = dp[i - 1][j] + dp[i][j - coins[i - 1]];
                    }else{
        
                        dp[i][j] = dp[i - 1][j];
                    }
                }
            }
            return dp[n][amount];
        }
    }

状态压缩后的代码：

class Solution {
        
        public int change(int amount, int[] coins) {
        
            int n = coins.length;
            int[] dp = new int[amount + 1];
            dp[0] = 1;
            for(int coin: coins){
        
                for(int j = coin; j <= amount; j++){
        
                        dp[j] = dp[j] + dp[j - coin];
                }
            }
            return dp[amount];
        }
    }

--------------------

### 322. 零钱兑换（中等） ###

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

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

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

**解题思路**：因为硬币可以重复使用，因此这是一个完全背包问题。完全背包只需要将 0-1 背包的逆序遍历 dp 数组改为正序遍历即可。

class Solution {
        
        public int coinChange(int[] coins, int amount) {
               
            int[] dp = new int[amount + 1];
            Arrays.fill(dp, amount + 1);
            dp[0] = 0;
            for(int coin: coins){
        
                for(int j = coin; j <= amount; j++){
        
                  dp[j] = Math.min(dp[j], dp[j - coin] + 1); 
                }
            }
            return dp[amount] == (amount + 1) ? -1 : dp[amount];
        }
    }

--------------------

### 139. 单词拆分（中等） ###

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

**说明：**

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

输入: s = "leetcode", wordDict = ["leet", "code"]
    输出: true
    解释: 返回 true 因为 "leetcode" 可以被拆分成 "leet code"。

输入: s = "applepenapple", wordDict = ["apple", "pen"]
    输出: true
    解释: 返回 true 因为 "applepenapple" 可以被拆分成 "apple pen apple"。
         注意你可以重复使用字典中的单词。

**解题思路**：完全背包问题：定义 `dp[i]`表示字符串 s 前 i 个字符组成的字符串 `s[0..i−1]` 是否能被空格拆分成若干个字典中出现的单词。

考虑状态转移方程，对于wordDict中的每个单词，我们可以选择拼接或者不拼接：

*  如果不拼接，那么`dp[i]`就应该取决于上一个`dp[i]`;
 *  如果选择拼接，首先求出这个单词的长度`len`，那么如果这个单词与字符串的`(i - len, i)`部分匹配，且`dp[i - len]`，即字符串的前`i-len`个字符也是可以拆分的，那么`dp[i - len]`就等于true；
 *  综上，状态转移方程为：`dp[i] = dp[i] || dp[i - len];`

class Solution {
        
        public boolean wordBreak(String s, List<String> wordDict) {
        
            int n = s.length();
            boolean[] dp = new boolean[n + 1];
            dp[0] = true; //base case
            for (int i = 1; i <= n; i++) {
        
                for (String word : wordDict) {
           // 对物品的迭代应该放在最里层
                    int len = word.length();
                    if (len <= i && word.equals(s.substring(i - len, i))) {
        
                        dp[i] = dp[i] || dp[i - len];
                    }
                }
            }
            return dp[n];
        }
    }

--------------------

### 377. 组合总和 IV（中等） ###

给你一个由 **不同** 整数组成的数组 `nums` ，和一个目标整数 `target` 。请你从 `nums` 中找出并返回总和为 `target` 的元素组合的个数。

题目数据保证答案符合 32 位整数范围。（注意：顺序不同的组合属于不同的组合）

输入：nums = [1,2,3], target = 4
    输出：7
    解释：
    所有可能的组合为：
    (1, 1, 1, 1)
    (1, 1, 2)
    (1, 2, 1)
    (1, 3)
    (2, 1, 1)
    (2, 2)
    (3, 1)
    **请注意，顺序不同的序列被视作不同的组合。**

**解题思路**：属于动态规划的完全背包问题，不同的是由于需要考虑选取元素的顺序，因此这道题需要计算的是选取元素的**排列**数。

用 `dp[x]`表示选取的元素之和等于 x 的方案数，目标是求 `dp[target]`。动态规划的边界是 `dp[0]=1`。只有当不选取任何元素时，元素之和才为 0，因此只有 1种方案。

当 `1≤i≤target` 时，如果存在一种排列，其中的元素之和等于 i，则该排列的最后一个元素一定是数组nums 中的一个元素。假设该排列的最后一个元素num，则一定有 `num≤i`，对于元素之和等于 `i−num` 的每一种排列，在最后添加 num 之后即可得到一个元素之和等于 i 的排列，因此在计算`dp[i]` 时，应该计算所有的 `dp[i−num]` 之和。

由此可以得到动态规划的做法：

*  初始化`dp[0]=1`；
 *  遍历 i 从 1 到 target，对于每个 i，进行如下操作：
    
     *  遍历数组 nums 中的每个元素num，当 `num≤i`时，将`dp[i−num]`的值加到`dp[i]`。
 *  最终得到`dp[target]`的值即为答案。

上述做法是否考虑到选取元素的顺序？答案是肯定的。因为外层循环是遍历从 1到 target 的值，内层循环是遍历数组 nums 的值，在计算 dp\[i\] 的值时，nums 中的每个小于等于 i 的元素都可能作为元素之和等于 ii的排列的最后一个元素。例如，1 和 3 都在数组 nums 中，计算 dp\[4\] 的时候，排列的最后一个元素可以是 1 也可以是 3，因此dp\[1\] 和 dp\[3\] 都会被考虑到，即不同的顺序都会被考虑到。  
[参考链接：leetcode官方题解][leetcode]

class Solution {
        
        public int combinationSum4(int[] nums, int target) {
        
            int[] dp = new int[target + 1];
            dp[0] = 1;//base case
            Arrays.sort(nums); //排序
            for(int i = 0; i<= target; i++){
        
                for(int num : nums){
        
                    if(num <= i){
        
                        dp[i] = dp[i] + dp[i - num];
                    }
                }
            }
            return dp[target];
        }
    }

--------------------

[Link 1]: https://leetcode-cn.com/problems/target-sum/solution/dong-tai-gui-hua-si-kao-quan-guo-cheng-by-keepal/
[Link 2]: https://leetcode-cn.com/problems/target-sum/solution/494-mu-biao-he-dong-tai-gui-hua-zhi-01be-78ll/
[leetcode]: https://leetcode-cn.com/problems/combination-sum-iv/solution/zu-he-zong-he-iv-by-leetcode-solution-q8zv/