动态规划

# 动态规划

动态规划的理论基础：代码随想录 (programmercarl.com) (opens new window)
主要的几个点：
- 确定dp数组（dp table）以及下标的含义
- 确定递推公式
- dp数组如何初始化
- 确定遍历顺序
- 举例推导dp数组

# 1、斐波那契数

# 1、题目

斐波那契数（通常用 F(n) 表示）形成的序列称为斐波那契数列。该数列由 0 和 1 开始，后面的每一项数字都是前面两项数字的和。也就是：
F(0) = 0，F(1) = 1
F(n) = F(n - 1) + F(n - 2)，其中 n > 1
1
2
给定 n ，请计算 F(n) 。

示例 1：
输入：n = 2
输出：1
解释：F(2) = F(1) + F(0) = 1 + 0 = 1
1
2
3
示例 2：
输入：n = 3
输出：2
解释：F(3) = F(2) + F(1) = 1 + 1 = 2
1
2
3
示例 3：
输入：n = 4
输出：3
解释：F(4) = F(3) + F(2) = 2 + 1 = 3
1
2
3
提示：

0 <= n <= 30

# 2、思路

动规五部曲：
这里我们要用一个一维dp数组来保存递归的结果
1. 确定dp数组以及下标的含义
  - dp[i]的定义为：第i个数的斐波那契数值是dp[i]
2. 确定递推公式为什么这是一道非常简单的入门题目呢？
  - 因为题目已经把递推公式直接给我们了：状态转移方程 dp[i] = dp[i - 1] + dp[i - 2];
3. dp数组如何初始化
  - 题目中把如何初始化也直接给我们了，如下：
```
dp[0] = 0;
dp[1] = 1;
```
1
2
1. 确定遍历顺序
  - 从递归公式dp[i] = dp[i - 1] + dp[i - 2];中可以看出，dp[i]是依赖 dp[i - 1] 和 dp[i - 2]，那么遍历的顺序一定是从前到后遍历的
2. 举例推导dp数组
  - 按照这个递推公式dp[i] = dp[i - 1] + dp[i - 2]，我们来推导一下，当N为10的时候，dp数组应该是如下的数列：
  - 0 1 1 2 3 5 8 13 21 34 55
如果代码写出来，发现结果不对，就把dp数组打印出来看看和我们推导的数列是不是一致的。

# 3、代码

//动态规划(非压缩)
int fib(int n){
   if(n<=1) return n;
   int *dp = (int*)malloc(sizeof(int)* (n+1));
   dp[0] = 0;
   dp[1] = 1;
   for(int i =2; i <= n; i++){
       dp[i]= dp[i-1] + dp[i-2];
   }
   return dp[n];
}

1
2
3
4
5
6
7
8
9
10
11

//动态规划(压缩)
int fib(int n){
   if(n<=1) return n;
   int dp[2];
   dp[0] = 0;
   dp[1] = 1;
   for(int i =2; i <= n; i++){
       int sum = dp[1] + dp[0];
       dp[0] = dp[1];
       dp[1] = sum;
   }
   return dp[1];
}

1
2
3
4
5
6
7
8
9
10
11
12
13

//递归解法
int fib(int n){
    if(n==0) return 0;
    if(n==1) return 1;
    int Fn = fib(n-1) + fib(n-2);
    return Fn;
}

1
2
3
4
5
6
7

# 2、爬楼梯

# 1、题目

假设你正在爬楼梯。需要 n 阶你才能到达楼顶。
每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？

示例 1：
输入：n = 2
输出：2
解释：有两种方法可以爬到楼顶。

1. 1 阶 + 1 阶
2. 2 阶
1
2
3
4
5
6
示例 2：
输入：n = 3
输出：3
解释：有三种方法可以爬到楼顶。

1. 1 阶 + 1 阶 + 1 阶
2. 1 阶 + 2 阶
3. 2 阶 + 1 阶
1
2
3
4
5
6
7
提示：

1 <= n <= 45

# 2、思路

动规五部曲：

1、确定dp数组以及下标的含义
- dp[i]：爬到第i层楼梯，有dp[i]种方法
2、确定递推公式

从dp[i]的定义可以看出，dp[i] 可以有两个方向推出来。

首先是dp[i - 1]，上i-1层楼梯，有dp[i - 1]种方法，那么再一步跳一个台阶不就是dp[i]了么。

还有就是dp[i - 2]，上i-2层楼梯，有dp[i - 2]种方法，那么再一步跳两个台阶不就是dp[i]了么。

那么dp[i]就是 dp[i - 1]与dp[i - 2]之和！

所以dp[i] = dp[i - 1] + dp[i - 2] 。
3、dp数组如何初始化
- 因为没有楼层0，或者说楼层是0，直接站楼顶上了，就是不用方法，dp[0]就应该是0.
- 所以我们就不考虑dp[0]如何初始化，只初始化dp[1] = 1，dp[2] = 2，然后从i = 3开始递推，这样才符合dp[i]的定义。
- 其实定义成dp[0],dp[1] 也是可以的，主要是看个人理解，我觉得定义，1和2比较贴合现实楼层对应关系，所以定义1和2
4、确定遍历顺序
- 从递推公式dp[i] = dp[i - 1] + dp[i - 2];中可以看出，遍历顺序一定是从前向后遍历的
5、举例推导dp数组
- 举例当n为5的时候，dp table（dp数组）应该是这样的

# 3、代码

int climbStairs(int n){
    // 因为我们直接从下标1开始遍历，所以要防止空指针
    if(n<=2) return n;
    int dp[3];
    dp[1] = 1;
    dp[2] = 2; 
    for(int i=3; i<=n; i++){
        int sum = dp[1] + dp[2];
        dp[1] = dp[2];
        dp[2] = sum;
    }
    return dp[2];
}

1
2
3
4
5
6
7
8
9
10
11
12
13

int climbStairs(int n){
    // 因为我们直接从下标1开始遍历，所以要防止空指针
    if(n<=2) return n;
    int *dp = (int*)malloc(sizeof(int)* (n+1));
    dp[1] = 1;
    dp[2] = 2; 
    for(int i=3; i<=n; i++){
        dp[i] = dp[i-1] + dp[i-2];
    }
    return dp[n];
}

1
2
3
4
5
6
7
8
9
10
11

# 3、使用最小花费爬楼梯

# 1、题目

给你一个整数数组 cost ，其中 cost[i] 是从楼梯第 i 个台阶向上爬需要支付的费用。一旦你支付此费用，即可选择向上爬一个或者两个台阶。

你可以选择从下标为 0 或下标为 1 的台阶开始爬楼梯。
请你计算并返回达到楼梯顶部的最低花费。

示例 1：
输入：cost = [10,15,20]
输出：15
解释：你将从下标为 1 的台阶开始。
  
- 支付 15 ，向上爬两个台阶，到达楼梯顶部。
  总花费为 15 。
1
2
3
4
5
6
示例 2：
输入：cost = [1,100,1,1,1,100,1,1,100,1]
输出：6
解释：你将从下标为 0 的台阶开始。
  
- 支付 1 ，向上爬两个台阶，到达下标为 2 的台阶。
- 支付 1 ，向上爬两个台阶，到达下标为 4 的台阶。
- 支付 1 ，向上爬两个台阶，到达下标为 6 的台阶。
- 支付 1 ，向上爬一个台阶，到达下标为 7 的台阶。
- 支付 1 ，向上爬两个台阶，到达下标为 9 的台阶。
- 支付 1 ，向上爬一个台阶，到达楼梯顶部。
  总花费为 6 
1
2
3
4
5
6
7
8
9
10
11
提示：

2 <= cost.length <= 1000

0 <= cost[i] <= 999

# 2、思路

这道题和爬楼梯 (opens new window)有类似的地方
确定dp数组以及下标的含义
- dp[i]的定义：到达第i台阶所花费的最少体力为dp[i]。
而到达刚开始两个楼层的代价为0，到达其他楼层的最小代价都是在到达其前面两个楼层的最小代价加上从这两个楼层向上爬所需花费进行比较的出来的

# 3、代码

int minCostClimbingStairs(int* cost, int costSize){
    // dp 为到达第i层台阶得最小代价
    int* dp = (int*)malloc(sizeof(int)* (costSize+1)); 
    dp[0] =0;
    dp[1] = 0;
    for(int i = 2;i <= costSize ;i++){   
        int sum1 = dp[i-1] + cost[i-1];
        int sum2 = dp[i-2] + cost[i-2];
        dp[i] = sum1 < sum2 ? sum1 : sum2 ;

    }
    return dp[costSize];
}

1
2
3
4
5
6
7
8
9
10
11
12
13

int minCostClimbingStairs(int* cost, int costSize){
    // dp 为到达第i层台阶得最小代价
    int dpBefore=0,dpAfter =0;
    for(int i = 2;i <= costSize ;i++){   
        int sum1 = dpAfter + cost[i-1];
        int sum2 = dpBefore + cost[i-2];
        dpBefore = dpAfter;
        dpAfter = sum1 < sum2 ? sum1 : sum2;

    }
    return dpAfter;
}

1
2
3
4
5
6
7
8
9
10
11
12

# 4、 0 - 1 背包理论基础

背包理论基础01背包（一） (opens new window) 二维dp数组

背包理论基础01背包（二） (opens new window) 一维dp数组

# 5、分割等和子集

# 1、题目

给你一个 只包含正整数 的非空数组 nums 。请你判断是否可以将这个数组分割成两个子集，使得两个子集的元素和相等。
示例 1：
输入：nums = [1,5,11,5]
输出：true
解释：数组可以分割成 [1, 5, 5] 和 [11] 。
1
2
3
4
示例 2：
输入：nums = [1,2,3,5]
输出：false
解释：数组不能分割成两个元素和相等的子集。
1
2
3
4
提示：
1 <= nums.length <= 200

1 <= nums[i] <= 100

# 2、思路

首先我们要清楚满足这道题的答案解法，这道题目是要找是否可以将这个数组分割成两个子集，使得两个子集的元素和相等。
那么只要找到集合里能够出现 sum / 2 的子集总和，就算是可以分割成两个相同元素和子集了。
要注意题目描述中商品是不是可以重复放入。

即一个商品如果可以重复多次放入是完全背包，而只能放入一次是01背包，写法还是不一样的。

要明确本题中我们要使用的是01背包，因为元素我们只能用一次。

回归主题：首先，本题要求集合里能否出现总和为 sum / 2 的子集。

那么来一一对应一下本题，看看背包问题如何来解决。
只有确定了如下四点，才能把01背包问题套到本题上来。
- 背包的体积为sum / 2
- 背包要放入的商品（集合里的元素）重量为元素的数值，价值也为元素的数值
- 背包如果正好装满，说明找到了总和为 sum / 2 的子集。
- 背包中每一个元素是不可重复放入。
以上分析完，我们就可以套用01背包，来解决这个问题了。

# 3、一维dp数组( 滚动数组 )

1. 确定dp数组以及下标的含义
- 01背包中，dp[j] 表示：容量为j的背包，所背的物品价值最大可以为dp[j]。
  
  本题中每一个元素的数值既是重量，也是价值。
  
  套到本题，dp[j]表示背包总容量（所能装的总重量）是j，放进物品后，背的最大重量为dp[j]。
  
  那么如果背包容量为target， dp[target]就是装满背包之后的重量，所以当 dp[target] == target 的时候，背包就装满了。
  
  有录友可能想，那还有装不满的时候？
  
  拿输入数组 [1, 5, 11, 5]，举例， dp[7] 只能等于 6，因为只能放进 1 和 5。
  
  而dp[6] 就可以等于6了，放进1 和 5，那么dp[6] == 6，说明背包装满了。
1. 确定递推公式
- 01背包的递推公式为：dp[j] = max(dp[j], dp[j - weight[i]] + value[i]);
  
  本题，相当于背包里放入数值，那么物品i的重量是nums[i]，其价值也是nums[i]。
  
  所以递推公式：dp[j] = max(dp[j], dp[j - nums[i]] + nums[i]);
1. dp数组如何初始化
- 在01背包，一维dp如何初始化，已经讲过，
  
  从dp[j]的定义来看，首先dp[0]一定是0。
  
  如果题目给的价值都是正整数那么非0下标都初始化为0就可以了，如果题目给的价值有负数，那么非0下标就要初始化为负无穷。
  
  这样才能让dp数组在递推的过程中取得最大的价值，而不是被初始值覆盖了。
  
  本题题目中只包含正整数的非空数组，所以非0下标的元素初始化为0就可以了。
1. 确定遍历顺序
- 在动态规划：关于01背包问题，你该了解这些！（滚动数组） (opens new window) (opens new window)中就已经说明：如果使用一维dp数组，物品遍历的for循环放在外层，遍历背包的for循环放在内层，且内层for循环倒序遍历！
1. 举例推导dp数组
- dp[j]的数值一定是小于等于j的。
  
  如果dp[j] == j 说明，集合中的子集总和正好可以凑成总和j，理解这一点很重要。
  
  用例1，输入[1,5,11,5] 为例，如图：
  
  最后dp[11] == 11，说明可以将这个数组分割成两个子集，使得两个子集的元素和相等。

/**
1. dp数组含义：dp[j]为背包重量为j时，其中可放入元素的最大值
2. 递推公式：dp[j] = max(dp[j], dp[j - nums[i]] + nums[i])
3. 初始化：均初始化为0即可
4. 遍历顺序：先遍历物品，再后序遍历背包
*/
#define MAX(a, b) (((a) > (b)) ? (a) : (b))

int getSum(int* nums, int numsSize) {
    int sum = 0;

    int i;
    for(i = 0; i < numsSize; ++i) {
        sum += nums[i];
    }
    return sum;
}

bool canPartition(int* nums, int numsSize){
    // 求出元素总和
    int sum = getSum(nums, numsSize);
    // 若元素总和为奇数，则不可能得到两个和相等的子数组
    if(sum % 2)
        return false;
    // 背包容量
    int target = sum / 2;

    // 初始化dp数组，元素均为0
    int dp[target + 1];
    memset(dp, 0, sizeof(int) * (target + 1));

    int i, j;
    // 先遍历物品，后遍历背包
    for(i = 0; i < numsSize; ++i) {
        for(j = target; j >= nums[i]; --j) {
            dp[j] = MAX(dp[j], dp[j - nums[i]] + nums[i]);
        }
    }
    
    // 查看背包容量为target时，元素总和是否等于target
    return dp[target] == target;
}

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
35
36
37
38
39
40
41
42

# 4、二维dp数组

/**
1. dp数组含义：dp[i][j]为背包重量为j时，从[0-i]元素和最大值
2. 递推公式：dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - nums[i]] + nums[i])
3. 初始化：dp[i][0]初始化为0。因为背包重量为0时，不可能放入元素。dp[0][j] = nums[0]，当j >= nums[0] && j < target时
4. 遍历顺序：先遍历物品，再遍历背包
*/
#define MAX(a, b) (((a) > (b)) ? (a) : (b))

int getSum(int* nums, int numsSize) {
    int sum = 0;

    int i;
    for(i = 0; i < numsSize; ++i) {
        sum += nums[i];
    }
    return sum;
}

bool canPartition(int* nums, int numsSize){
    // 求出元素总和
    int sum = getSum(nums, numsSize);
    // 若元素总和为奇数，则不可能得到两个和相等的子数组
    if(sum % 2)
        return false;

    // 若子数组的和等于target，则nums可以被分割
    int target = sum / 2;
    // 初始化dp数组
    int dp[numsSize][target + 1];
    // dp[j][0]都应被设置为0。因为当背包重量为0时，不可放入元素
    memset(dp, 0, sizeof(int) * numsSize * (target + 1));

    int i, j;
    // 当背包重量j大于nums[0]时，可以在dp[0][j]中放入元素nums[0]
    for(j = nums[0]; j <= target; ++j) {
        dp[0][j] = nums[0];
    }

    for(i = 1; i < numsSize; ++i) {
        for(j = 1; j <= target; ++j) {
            // 若当前背包重量j小于nums[i]，则其值等于只考虑0到i-1物品时的值
            if(j < nums[i])
                dp[i][j] = dp[i - 1][j];
            // 否则，背包重量等于在背包中放入num[i]/不放入nums[i]的较大值
            else
                dp[i][j] = MAX(dp[i - 1][j], dp[i - 1][j  - nums[i]] + nums[i]);
        }
    }
    // 判断背包重量为target，且考虑到所有物品时，放入的元素和是否等于target
    return dp[numsSize - 1][target] == target;
}

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
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51

# 6、最后一块石头的重量II

# 1、题目

有一堆石头，用整数数组 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
2
3
4
5
6
7
8
9
10
11
12
提示：

1 <= stones.length <= 30

1 <= stones[i] <= 100

# 2、思路

本题其实就是尽量让石头分成重量相同的两堆，相撞之后剩下的石头最小，这样就化解成01背包问题了。
- 和416. 分割等和子集 (opens new window) (opens new window)非常像了。
- 本题物品的重量为stones[i]，物品的价值也为stones[i]。
- 对应着01背包里的物品重量weight[i]和物品价值value[i]。
最后dp[target]里是容量为target的背包所能背的最大重量。

那么分成两堆石头，一堆石头的总重量是dp[target]，另一堆就是sum - dp[target]。

在计算target的时候，target = sum / 2 因为是向下取整，所以sum - dp[target] 一定是大于等于dp[target]的。

那么相撞之后剩下的最小石头重量就是 (sum - dp[target]) - dp[target]。

# 3、代码

# 二维：

/**
1. dp数组含义：dp[i][j]为背包重量为j时，从[0-i]元素和最大值
2. 递推公式：dp[i][j] = MAX(dp[i - 1][j], dp[i - 1][j - stones[i]] + stones[i])
3. 初始化：dp[i][0]初始化为0。因为背包重量为0时，不可能放入元素。dp[0][j] = nums[0]，当j >= nums[0] && j < target时
4. 遍历顺序：先遍历物品，再遍历背包
*/

#define MAX(a, b) (((a) > (b)) ? (a) : (b))

int getSum(int *stones, int stoneSize) {
    int sum = 0, i;
    for (i = 0; i < stoneSize; ++i)
        sum += stones[i];
    return sum;
}


int lastStoneWeightII(int* stones, int stonesSize){
    int sum = getSum(stones,stonesSize);
    int target = sum / 2;
    int i, j;

    //初始化dp数组
    int dp[stonesSize][target + 1];
    //注意二维数组初识化和一维数组的区别
    memset(dp, 0, sizeof(int)*stonesSize*(target + 1));
    for(j = stones[0];j <= target ;++j){
        dp[0][j] = stones[0];
    }

    //递推公式：dp[i][j] = MAX(dp[i - 1][j], dp[i - 1][j - stones[i]] + stones[i])
    //遍历顺序，先遍历物品，再遍历背包
    for(i = 1;i < stonesSize; ++i){
        for(j = 1 ;j <= target; ++j){
           if(j < stones[i]){
               dp[i][j] = dp[i-1][j];
           }
           else {
                dp[i][j] = MAX(dp[i - 1][j], dp[i - 1][j - stones[i]] + stones[i]);
           }
        }
    }
    return sum - dp[stonesSize - 1][target]- dp[stonesSize - 1][target];
}

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
35
36
37
38
39
40
41
42
43
44

# 一维：

/**
1. dp数组含义：dp[j]表示容量（这里说容量更形象，其实就是重量）为j的背包，最多可以背最大重量为dp[j]。
2. 递推公式：dp[j] = max(dp[j], dp[j - stones[i]] + stones[i])
3. 初始化：均初始化为0即可
4. 遍历顺序：先遍历物品，再后序遍历背包
*/

#define MAX(a, b) (((a) > (b)) ? (a) : (b))

int getSum(int *stones, int stoneSize) {
    int sum = 0, i;
    for (i = 0; i < stoneSize; ++i)
        sum += stones[i];
    return sum;
}


int lastStoneWeightII(int* stones, int stonesSize){
    int sum = getSum(stones,stonesSize);
    int target = sum / 2;
    int i, j;

    //初始化dp数组
    int *dp = (int*)malloc(sizeof(int)*(target +1));
    memset(dp, 0, sizeof(int)*(target + 1));
    for(j = stones[0];j <= target ;++j){
        dp[j] = stones[0];
    }

    //递推公式：dp[j] = max(dp[j], dp[j - stones[i]] + stones[i])
    //遍历顺序，先遍历物品，再遍历背包
    for(i = 1;i < stonesSize; ++i){
        for(j = target;j >= stones[i]; --j){
            dp[j] = MAX(dp[j], dp[j - stones[i]] + stones[i]);
        }
    }
    return sum - dp[target]- dp[target];
}

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
35
36
37
38

# 7、目标和

# 1、题目

给你一个整数数组 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
2
3
4
5
6
7
8
9
10
11
12
13
14
提示：

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

# 2、思路（二维）

记数组的元素和为sum, 添加-号的元素之和为neg,则其余添加+的元素之和为sum- neg,得到的表达式的结果为：
- (sum − neg) − neg = sum−2 * neg = target
- 即 neg = （sum - target）/ 2
由于数组nums中的元素都是非负整数, neg 也必须是非负整数,所以上式成立的前提是sum - target是非负偶数。若不符合该条件可直接返回0。
若上式成立,问题转化成在数组nums中选取若千元素,使得这些些素之和等于neg,计算选取元素的方案数。我们可以使用动态规划的方法求解。
定义二维数组dp，中dp[i][j] 表示在数组nums的前i个数中选取元素，使得这些元素之和等于j的方案数。假设数组nums的长度为n,则最终答案为dp[n][neg]。
当没有任何元素可以选取时，元愫和只能是0,对应的方案数是1,因此动态规划的边界条件是:
- 当 j = 0 时， dp[0][j] = 1 ;
- 当 j >= 1 时， dp[0][j] = 0 ;
当1≤i≤n时，对于数组nums中的第i个元素num (i 的计数从1开始)，遍历0≤j≤neg，计算dp[i][j]的值:
- 如果 j< num,则不能选num, 此时有 dp[i][j]= dp[i - 1][j];
- 如果 j≥num, 则
  - 如果不选num,案数是 dp[i- 1][j]，
  - 如果选num,方案数是dp[i- 1][j - num], 此时有dp[i][j]= dp[i- 1][j] + dp[i - 1][j - num]。
最终得到 dp[n][neg] 的值即为答案。

int findTargetSumWays(int* nums, int numsSize, int target) {
    int sum = 0;
    for (int i = 0; i < numsSize; i++) {
        sum += nums[i];
    }
    int diff = sum - target;
    // 以下两种情况就是没有方案
    if (diff < 0 || diff % 2 != 0) {
        return 0;
    }
    int n = numsSize, neg = diff / 2;
    int dp[n + 1][neg + 1];
    memset(dp, 0, sizeof(dp));
    dp[0][0] = 1;
    for (int i = 1; i <= n; i++) {
        int num = nums[i - 1];
        for (int j = 0; j <= neg; j++) {
            dp[i][j] = dp[i - 1][j];
            if (j >= num) {
                dp[i][j] += dp[i - 1][j - num];
            }
        }
    }
    return dp[n][neg];
}

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

于dp的每-行的计算只和上一行有关,因此可以使用滚动数组的方式，去掉dp的第一个维度，将空间复杂度优化到O(neg)。
实现时，内层循环需采用倒序遍历的方式，这种方式保证转移来的是dp[i - 1]0 中的元素值。

int findTargetSumWays(int* nums, int numsSize, int target) {
    int sum = 0;
    for (int i = 0; i < numsSize; i++) {
        sum += nums[i];
    }
    int diff = sum - target;
    if (diff < 0 || diff % 2 != 0) {
        return 0;
    }
    int neg = diff / 2;
    int dp[neg + 1];
    memset(dp, 0, sizeof(dp));
    dp[0] = 1;
    for (int i = 0; i < numsSize; i++) {
        int num = nums[i];
        for (int j = neg; j >= num; j--) {
            dp[j] += dp[j - num];
        }
    }
    return dp[neg];
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

编辑

上次更新: 2023/09/13, 12:29:52

← 贪心算法 KMP算法→