总体认识⁍

动态规划包含了「分治思想」、「空间换时间」、「最优解」等多种基石算法思想

  • 动态规划问题特点，动态规划和分治算法的联系与区别；
  • 借助例题介绍重叠子问题和最优子结构分别是什么，以及动态规划是如何解决它们的；
  • 动态规划的解题框架总结；
  • 动态规划的练习例题，从易到难排序；

普遍来看，求最值 的问题一般都具有「重叠子问题」和「最优子结构」特点，因此此类问题往往适合用动态规划解决。

动态规划特点⁍

「分治」是算法中的一种基本思想，其通过将原问题分解为子问题，不断递归地将子问题分解为更小的子问题，并通过组合子问题的解来得到原问题的解。

类似于分治算法，**「动态规划」也通过组合子问题的解得到原问题的解。不同的是，适合用动态规划解决的问题具有「重叠子问题」和「最优子结构」**两大特性。

1. 重叠子问题⁍

各个子问题中包含重复的更小子问题。

  • 第一次求解某子问题时，保存子问题的解

  • 后续遇到重叠子问题时，则直接通过查表获取解

示例：斐波那契数列⁍

斐波那契数形成的数列为 [0,1,1,2,3,5,8,13,⋯]

F0=0

F1=1

Fn=Fn-1+Fn-2

求第N个斐波那契数（从第0个开始）

  • 暴力递归：fibonacci() 函数的调用次数$O(2^n)$
  • 记忆化递归：用数组保存子问题的解：fibonacci() 函数的调用次数$O(n)$
  • 动态规划：循环迭代
    • 数组保存dp[i]：空间复杂度$O(N)$
    • 使用两个变量 a,b交替前进计算：空间复杂度$O(1)$

不包含「最优子结构」，并不需要从子问题组合中选择最优组合。

2. 最优子结构⁍

如果

  1. 一个问题的最优解可以由其子问题的最优解组合构成，并且
  2. 这些子问题可以独立求解，

那么称此问题具有最优子结构。

动态规划从基础问题的解开始，不断迭代组合、选择子问题的最优解，最终得到原问题最优解。

最优子结构示例：蛋糕最高售价⁍

image-20211219194207921

设重量为$n$蛋糕的售价为$p(n)$ ，切分的最高总售价为$f(n)$

$f(n) = \max_{0 \leq i < n} (f(i) + p(n - i))$

1
2
3
4
5
6
7
8
9
10
11
// 输入蛋糕价格列表 priceList ，求重量为 n 蛋糕的最高售价
int maxCakePrice(int n, int[] priceList) {
    if (n <= 1) return priceList[n];  // 蛋糕重量 <= 1 时直接返回
    int[] dp = new int[n + 1];        // 初始化 dp 列表
    for (int j = 1; j <= n; j++) {    // 按顺序计算 f(1), f(2), ..., f(n)
        for (int i = 0; i < j; i++)   // 从 j 种组合种选择最高售价的组合作为 f(j)
            dp[j] = Math.max(dp[j], dp[i] + priceList[j - i]);
    }
    return dp[n];
}

动态规划解题框架⁍

若确定给定问题具有重叠子问题和最优子结构，那么就可以使用动态规划求解。总体上看，求解可分为四步：

  1. 状态定义： 构建问题最优解模型，包括问题最优解的定义、有哪些计算解的自变量；
  2. 初始状态： 确定基础子问题的解（即已知解），原问题和子问题的解都是以基础子问题的解为起始点，在迭代计算中得到的；
  3. 转移方程： 确定原问题的解与子问题的解之间的关系是什么，以及使用何种选择规则从子问题最优解组合中选出原问题最优解；
  4. 返回值： 确定应返回的问题的解是什么，即动态规划在何处停止迭代；

完成以上步骤后，便容易写出对应的解题代码。

示例：斐波那契数列⁍

  • 状态定义：一维dp列表，设第i 个斐波那契数为dp[i]
  • 初始状态：dp[0]=0, dp[1]=1
  • 转移方程：dp[i]=dp[i-1]+dp[i-2]
  • 返回值：需求取的第n个斐波那契数dp[n]

示例：蛋糕最高售价⁍

  • 状态定义：一维dp列表，设重量为i的蛋糕的售价为p(i)，重量为i的蛋糕切分后的最高售价为 dp[i]

  • 初始状态：dp[0]=0, dp[1]=p[1]

  • 转移方程：

    $$f(n) = \max_{0 \leq i < n} (f(i) + p(n - i))$$

  • 返回值：需求取的重量为n的蛋糕最高售价$dp[n]$

动态规划五部曲⁍

递推公式决定了dp数组要如何初始化 [1]

  1. 确定dp数组（dp table）以及下标的含义
  2. 确定递推公式
  3. dp数组如何初始化
  4. 确定遍历顺序
  5. 举例推导dp数组

背包问题⁍

总结图[1:1]

img

常见的背包类型主要有以下几种[2]：
1、0/1背包问题：每个元素最多选取一次
2、完全背包问题：每个元素可以重复选择
3、排列（组合）背包问题：背包中的物品要考虑顺序
4、分组背包问题：不止一个背包，需要遍历每个背包

而每个背包问题要求的也是不同的，按照所求问题分类，又可以分为以下几种：
1、最值问题：要求最大值/最小值
2、存在问题：是否存在…………，满足…………
3、组合问题：求所有满足……的排列组合

因此把背包类型和问题类型结合起来就会出现以下细分的题目类型：
1、0/1背包最值问题
2、0/1背包存在问题
3、0/1背包组合问题
4、完全背包最值问题
5、完全背包存在问题
6、完全背包组合问题
7、分组背包最值问题
8、分组背包存在问题
9、分组背包组合问题这九类问题我认为几乎可以涵盖力扣上所有的背包问题

0-1背包问题⁍

有n件物品和一个最多能背重量为w 的背包。第i件物品的重量是weight[i]，得到的价值是value[i] 。每件物品只能用一次，求解将哪些物品装入背包里物品价值总和最大。

举例：背包最大重量为4。

重量 价值
物品0 1 15
物品1 3 20
物品2 4 30

问背包能背的物品最大价值是多少？

思路：

二维dp数组⁍

  1. 确定dp数组（dp table）以及下标的含义

    dp[i][j] 表示从 下标为[0-i]的物品 里任意取，放进 容量为j 的背包，价值总和最大是多少

    image-20220307145059850

  2. 确定递推公式

    • j < weight[i]: 放不了物品：

      • dp[i][i]=dp[i-1][j]

    • j >= weight[j]: max(不放物品i，放物品i)

      放物品i = value(物品i)+在剩余重量（j-物品i重量）里放其他物品

      dp[i][j] = max(dp[i-1][j], v[i]+dp[i-1][j-weight[i]])

  3. dp数组如何初始化

    dp[i][0] = 0

    dp[0][j]:

    • j < weight[0]: 0
    • j >= weight[i]: v[0]

  4. 确定遍历顺序

    都可以，例如先遍历物品，再遍历重量

  5. 举例推导dp数组

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
public static void main(String[] args) {
    int[] weight = {1, 3, 4};
    int[] value = {15, 20, 30};
    int bagsize = 4;
    testweightbagproblem(weight, value, bagsize);
}

public static void testweightbagproblem(int[] weight, int[] value, int bagsize){
    int m = weight.length; // 一共有多少物品，决定dp行数
    int n = bagsize+1; // 背包重量，决定dp列数, 记得+1
    int[][] dp = new int[m][n];

    for(int i = 0; i < m; i++){
        dp[i][0] = 0; // 初始化
    }
    for (int j = 0; j < n; j++) {
        if (j < weight[0]) {
            dp[0][j] = 0;
        }else{
            dp[0][j] = value[0];
        }
    }
    for(int i = 1; i < m; i++ ){
        for(int j=1; j<n; j++){
            if(j<weight[i]){
                dp[i][j] = dp[i-1][j];
            }else{
                dp[i][j] = Math.max(dp[i-1][j], value[i]+dp[i-1][j-weight[i]]);
            }
        }
    }
    System.out.println(dp[m-1][n-1]);
}

滚动数组——dp降维⁍

对于Math.max(dp[i-1][j], value[i]+dp[i-1][j-weight[i]])

dp[i-1]这一层可以拷贝到dp[i]这层上滚动:

dp[j] = Math.max(dp[j], dp[j - weight[i]] + value[i]);

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

public static void main(String[] args) {
    int[] weight = {1, 3, 4};
    int[] value = {15, 20, 30};
    int bagsize = 4;
    testweightbagproblem(weight, value, bagsize);
}

public static void testweightbagproblem(int[] weight, int[] value, int bagsize){
    int m = weight.length; // 一共有多少物品
    int n = bagsize+1; // 背包重量，决定dp列数, 记得+1
    int[] dp = new int[n];

    dp[0] = 0;
    for (int j = 0; j < n; j++) {
        if (j < weight[0]) {
            dp[j] = 0;
        }else{
            dp[j] = value[0];
        }
    }
    for(int i = 1; i < m; i++ ){
        for(int j=1; j<n; j++){
            if(j<weight[i]){
                dp[j] = dp[j];
            }else{
                dp[j] = Math.max(dp[j], value[i]+dp[j-weight[i]]);
            }
        }
    }
    System.out.println(dp[n-1]);
}

分类解题模板⁍

背包问题大体的解题模板是两层循环，分别遍历物品nums和背包容量target，然后写转移方程，根据背包的分类我们确定物品和容量遍历的先后顺序，根据问题的分类我们确定状态转移方程的写法[2:1]

首先是背包分类的模板：⁍

1、 0/1背包： 外循环nums,内循环target,target倒序且target>=nums[i];
2、 完全背包（可重复）： 外循环nums,内循环target,target正序且target>=nums[i];
3、 排序（组合）背包/属于完全背包： 外循环target,内循环nums,target正序且target>=nums[i];
4、 分组背包： 这个比较特殊，需要三重循环：外循环背包bags,内部两层循环根据题目的要求转化为1,2,3三种背包类型的模板

如果求组合数就是外层for循环遍历物品，内层for遍历背包。

如果求排列数就是外层for遍历背包，内层for循环遍历物品。

然后是问题分类的模板：⁍

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];

这样遇到问题将两个模板往上一套大部分问题就可以迎刃而解

53. 最大子数组和⁍

Leetcode|数组Arrays

55. 跳跃游戏⁍

给定一个非负整数数组 nums ，你最初位于数组的 第一个下标 。

数组中的每个元素代表你在该位置可以跳跃的最大长度。

判断你是否能够到达最后一个下标。

思路：（较慢）

  • 状态定义：

    • $n[i]$: nums[i]的值
    • $r[i]$: i结点能否到达

  • 初始状态：$r[0]=1$

  • 转移方程：$$r[n]=r[i]\And\And n[i]>=n-i, 0<=i<n$$

  • 返回值：true/false

70. 爬楼梯⁍

假设你正在爬楼梯。需要 n 阶你才能到达楼顶。

每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？

注意：给定 n 是一个正整数。

思路： 相当于斐波那契数列

  1. 确定dp数组（dp table）以及下标的含义

    dp[i]： 爬到第i层有多少种方法

  2. 确定递推公式

    dp[i] = dp[i-1] + dp[i-2]

    i-1层爬1个台阶，i-2层爬2个台阶

  3. dp数组如何初始化

    dp[1] = 1

    dp[2] = 2

  4. 确定遍历顺序

    从小到大

  5. 举例推导dp数组

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
    public int climbStairs(int n) {
        // 跟斐波那契数列一样
        if(n <= 2) return n;
        int a = 1, b = 2, sum = 0;
        
        for(int i = 3; i <= n; i++){
            sum = a + b;
            a = b;
            b = sum;
        }
        return b;
    }
}

746. 使用最小花费爬楼梯⁍

数组的每个下标作为一个阶梯，第 i 个阶梯对应着一个非负数的体力花费值 cost[i]（下标从 0 开始）。

每当你爬上一个阶梯你都要花费对应的体力值，一旦支付了相应的体力值，你就可以选择向上爬一个阶梯或者爬两个阶梯。

请你找出达到楼层顶部的最低花费。在开始时，你可以选择从下标为 0 或 1 的元素作为初始阶梯。

思路

dp[i] = min(dp[i - 1] + cost[i - 1], dp[i - 2] + cost[i - 2])

1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
    public int minCostClimbingStairs(int[] cost) {
        int a = 0; // 爬到第0级的花销
        int b = 0; // 爬到第1级的花销
        int sum = 0;
        for (int i = 2; i <= cost.length; i++) {
            sum = Math.min(a + cost[i - 2], b + cost[i - 1]);
            a = b;
            b = sum;
        }
        return sum;
    }

62. 不同路径⁍

一个机器人位于一个 m x n 网格的左上角 （起始点在下图中标记为 “Start” ）。

机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为 “Finish” ）。

问总共有多少条不同的路径？

思路

dp[i][j] = dp[i-1][j] + dp[i][j-1]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
    public int uniquePaths(int m, int n) {
        int[][] dp = new int[m][n];
        dp[0][0] = 1;
        for (int i = 0; i < m; i++) {
            dp[i][0] = 1;
        }
        for (int j = 0; j < n; j++) {
            dp[0][j] = 1;
        }
        for (int i = 1; i < m; i++) {
            for (int j = 1; j < n; j++) {
                dp[i][j] = dp[i-1][j]+dp[i][j-1];
            }
        }
        return dp[m-1][n-1];
    }
}

63. 不同路径 II⁍

网格中有障碍物

网格中的障碍物和空位置分别用 1 和 0 来表示。

img

如果有障碍物则置0

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
class Solution {
    public int uniquePathsWithObstacles(int[][] obstacleGrid) {
        int m = obstacleGrid.length;
        int n = obstacleGrid[0].length;
        obstacleGrid[0][0] = obstacleGrid[0][0]^1; //0变1，1变0
        for (int i = 1; i < m; i++) {
            if (obstacleGrid[i][0] == 1) { // 有障碍物，说明不可达
                obstacleGrid[i][0] = 0; // 置0
            }else{
                obstacleGrid[i][0] = obstacleGrid[i-1][0];
            }

        }
        for (int j = 1; j < n; j++) {
            if (obstacleGrid[0][j] == 1) {
                obstacleGrid[0][j] = 0;
            }else {
                obstacleGrid[0][j] = obstacleGrid[0][j-1];
            }
        }
        for (int i = 1; i < m; i++) {
            for (int j = 1; j < n; j++) {
                if (obstacleGrid[i][j] == 1) {
                    obstacleGrid[i][j] = 0;
                } else {
                    obstacleGrid[i][j] = obstacleGrid[i-1][j] + obstacleGrid[i][j-1];
                }
            }
        }

        return obstacleGrid[m-1][n-1];
    }
}

343. 整数拆分⁍

给定一个正整数 n，将其拆分为至少两个正整数的和，并使这些整数的乘积最大化。 返回你可以获得的最大乘积。

思路

1. 数学方法

可以用数学归纳法证明对任意一个整数最大的拆分形式为n = 2p + 3q，则乘积 m = 2^p * 3^q (n >= 3, p, q为自然数)，并且q应该尽可能大（理由：如果q减少2，则p要增加3，而2^3 < 3^2，因此应该尽可能增加q）。

–》动态规划

1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
    public int integerBreak(int n) {
        if (n < 4) return n - 1;     
        int[] dp = new int[n + 1];        
        dp[2] = 2;
        dp[3] = 3;
        for (int i = 4; i <= n; i++) {
            dp[i] = Math.max(dp[i - 2] * 2, dp[i - 3] * 3);
        }
        return dp[n];
    }
}

image-20220307110751766

–> 直接数学

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
    public int integerBreak(int n) {
        if (n <= 3) {
            return n - 1;
        }
        int quotient = n / 3;
        int remainder = n % 3;
        if (remainder == 0) {
            return (int) Math.pow(3, quotient);
        } else if (remainder == 1) {
            return (int) Math.pow(3, quotient - 1) * 4;
        } else {
            return (int) Math.pow(3, quotient) * 2;
        }
    }
}

2. 动态规划

  1. 确定dp数组（dp table）以及下标的含义

    dp[i]：分拆数字i，可以得到的最大乘积为dp[i]。

  2. 确定递推公式

    有两种渠道得到dp[i].

    一个是j * (i - j) 直接相乘。

    一个是j * dp[i - j]，相当于是拆分(i - j)

    dp[i] = max(dp[i], max((i - j) * j, dp[i - j] * j));

    在遍历过程中不断更新dp[i]的最大值

  3. dp的初始化

    dp[2] = 1,// dp[3] = 2

  4. 确定遍历顺序

    从前向后

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
    public int integerBreak(int n) {
        int[] dp = new int[n + 1];
        for (int i = 2; i <= n; i++) {
            int curMax = 0;
            for (int j = 1; j < i; j++) {
                curMax = Math.max(curMax, Math.max(j * (i - j), j * dp[i - j]));
            }
            dp[i] = curMax;
        }
        return dp[n];
    }
}

96. 不同的二叉搜索树⁍

给你一个整数 n ，求恰由 n 个节点组成且节点值从 1 到 n 互不相同的 二叉搜索树 有多少种？返回满足题意的二叉搜索树的种数。

示例 1：

img

1
2
输入：n = 3
输出：5

示例 2：

1
2
输入：n = 1
输出：1

思路：

  1. 确定dp数组（dp table）以及下标的含义

    dp[i]: 从 1 到 i 互不相同的 二叉搜索树

  2. 确定递推公式

    在从1-i-1的二叉搜索树中加入i节点，根节点一共有i种可能：

    • 根节点是i：没有元素比它大，右子树为空；1~i-1都比它小，成为它的左子树。一共是dp[i-1]种
    • 根节点是i-1：i比i-1大，右子树1个节点dp[1]；1~i-2都比它小，左子树i-2个节点，即dp[i-2]。一共是dp[1]*dp[i-2]种。
    • 根节点是i-2：i-1~i比i-2大，右子树2个节点dp[2]；…左子树i-3个节点，即dp[i-3]。一共dp[2]*dp[i-3]
    • …

    综合，取dp[0]=1；则

    dp[i] = sum(dp[j]*dp[i-j-1])，j=0,…,i-1

  3. dp数组如何初始化

    dp[1] = 1

  4. 确定遍历顺序

    从小到大

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
    public int numTrees(int n) {
        if (n == 1) {
            return 1;
        }
        int[] dp = new int[n+1];
        dp[0] = 1;
        dp[1] = 1;
        for (int i = 2; i <= n ; i++) {
            for (int j = 0; j < i; j++) {
                dp[i] += dp[j]*dp[i-j-1];
            }
        }
        return dp[n];
    }
}

416. 分割等和子集⁍

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

示例 1：

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

示例 2：

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

提示：

  • 1 <= nums.length <= 200
  • 1 <= nums[i] <= 100

思路： 转化为0-1背包

先计算sum，sum为单数则直接返回false

target = sum/2

先排序？

  1. dp数组

    dp[j]表示最大（接近）为j时的和

  2. 递推公式

    • nums[i]>j: 加不进去
    • nums[i]<=j:
      • max()
      • dp[j]
      • nums[i]+dp[j-nums[i]]

  3. 初始状态

    如果如果题目给的价值都是正整数那么非0下标都初始化为0就可以了，如果题目给的价值有负数，那么非0下标就要初始化为负无穷。

    这样才能让dp数组在递归公式的过程中取的最大的价值，而不是被初始值覆盖了。

  4. 遍历顺序

    从大到小遍历

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
    public boolean canPartition(int[] nums) {
        int n = nums.length;
        int sum = 0;
        for (int num: nums) {
            sum+=num;
        }
        if ((sum & 1) ==1) {
            return false;
        }
        int target = sum/2;
        int[] dp = new int[target+1];
        for (int i = 0; i < n; i++) {
            for (int j = target; j >= nums[i] ; j--) { // 注意倒序遍历
                dp[j] = Math.max(dp[j], nums[i]+dp[j-nums[i]]);
            }
            if (dp[target] == target) {
                return true;
            }
        }
        return false;
    }
}

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

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

每一回合，从中选出任意两块石头，然后将它们一起粉碎。假设石头的重量分别为 x 和 y，且 x <= y。那么粉碎的可能结果如下：

  • 如果 x == y，那么两块石头都会被完全粉碎；
  • 如果 x != y，那么重量为 x 的石头将会完全粉碎，而重量为 y 的石头新重量为 y-x。

最后，最多只会剩下一块 石头。返回此石头 最小的可能重量 。如果没有石头剩下，就返回 0。

示例 1：

1
2
3
4
5
6
7
输入：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：

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

示例 3：

1
2
输入：stones = [1,2]
输出：1

提示：

  • 1 <= stones.length <= 30
  • 1 <= stones[i] <= 100

思路 问题转化为：把一堆石头分成两堆,求两堆石头重量差最小值

要让差值小,两堆石头的重量都要接近sum/2;

将一堆stone放进最大容量为sum/2的背包,求放进去的石头的最大重量MaxWeight, 最终答案即为 sum-2*MaxWeight

dp[i][j]含义:从前i块石头中选取，选取值之和小于等于目标值j的最大值为dp。（i、j分别对应从外到内两层循环。）（maxWeight）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
    public int lastStoneWeightII(int[] stones) {
        int sum = 0;
        for (int stone:stones) {
            sum+=stone;
        }
        int target = sum/2;
        int[] dp = new int[target+1];
        for (int i = 0; i < stones.length; i++) {
            for (int j = target; j >=stones[i] ; j--) {
                dp[j] = Math.max(dp[j], dp[j-stones[i]]+stones[i]);
            }
        }
        return sum-2*dp[target];
    }
}

494. 目标和⁍

给你一个整数数组 nums 和一个整数 target 。

向数组中的每个整数前添加 '+' 或 '-' ，然后串联起所有整数，可以构造一个 表达式 ：

  • 例如，nums = [2, 1] ，可以在 2 之前添加 '+' ，在 1 之前添加 '-' ，然后串联起来得到表达式 "+2-1" 。

返回可以通过上述方法构造的、运算结果等于 target 的不同 表达式 的数目。

示例 1：

1
2
3
4
5
6
7
8
输入：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：

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

提示：

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

思路 0-1背包组合问题

数组和sum,目标和s, 正数的和为x,负数的和为-y,则x+y=sum,x-y=s,那么x=(s+sum)/2=target

在本题中，s换名叫target，这里target就更正为tt

相当于在nums里选x个数，和为tt

初始化 dp[0]=1

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
    public int findTargetSumWays(int[] nums, int target) {
        int sum = 0;
        for (int num:nums) {
            sum += num;
        }
        // 先判断target是否存在
        if (((sum + target)&1)==1 || sum <target || -sum>target) {
            return 0;
        }
        int tt = (target+sum)/2;
        int[] dp = new int[tt+1];
        dp[0] = 1;
        for (int num:nums) {
            for (int i = tt; i >=num ; i--) {
                dp[i] += dp[i-num];
            }
        }
        return dp[tt];
    }
}

474. 一和零⁍

给你一个二进制字符串数组 strs 和两个整数 m 和 n 。

请你找出并返回 strs 的最大子集的长度，该子集中 最多 有 m 个 0 和 n 个 1 。

如果 x 的所有元素也是 y 的元素，集合 x 是集合 y 的 子集 。

示例 1：

1
2
3
4
输入：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：

1
2
3
输入：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

思路： 0-1背包 最值问题

三维–》二维

dp[i][j] 子集长度; 有i个0，j个1

dp[0][0]：0（空集）

返回的是子集的长度！不是字符串的长度！

dp[i][j] = Math.max(dp[i][j], dp[i-s.zero][j-s.one]+1);

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
class Solution {
    public int findMaxForm(String[] strs, int m, int n) {
        int[][] dp = new int[m+1][n+1];
        dp[0][0] = 0;
        for (String str:strs) {
            MyString s = new MyString(str);
            for (int i = m; i >=s.zero ; i--) {
                for (int j = n; j >=s.one ; j--) {
                    dp[i][j] = Math.max(dp[i][j], dp[i-s.zero][j-s.one]+1);
                }
            }
        }
        return dp[m][n];
    }

    class MyString {
        int zero; // 0的数量
        int one; // 1的数量
        String val; // 值
        int length;
        MyString(String str){
            this.val = str;
            this.length = str.length();
            this.one = this.cntOne(this.val);
            this.zero = this.length - this.one;
        }

        private int cntOne(String str){
            // 不能转换为整数来count，因为可能整型溢出
            int k = 0;
            for (int i = 0; i < str.length(); i++) {
                if (str.charAt(i) == '1') {
                    k++;
                }
            }
            return k;
        }
    }
}

322. 零钱兑换⁍

给你一个整数数组 coins ，表示不同面额的硬币；以及一个整数 amount ，表示总金额。

计算并返回可以凑成总金额所需的 最少的硬币个数 。如果没有任何一种硬币组合能组成总金额，返回 -1 。

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

示例 1：

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

示例 2：

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

示例 3：

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

提示：

  • 1 <= coins.length <= 12
  • 1 <= coins[i] <= 231 - 1
  • 0 <= amount <= 104

思路： 完全背包 最值问题

dp[i] 代表组成金额i的最少硬币个数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
    public int coinChange(int[] coins, int amount) {
        int maxVal = amount+1;
        if (amount == 0) {
            return 0;
        }
        int[] dp = new int[amount+1];
        Arrays.fill(dp, maxVal); // 初始化
        dp[0] = 0;
        for (int coin:coins) {
            for (int i = coin; i <= amount; i++) {
                dp[i] = Math.min(dp[i], dp[i-coin]+1);
            }
        }
        return dp[amount] == maxVal ? -1 : dp[amount];
    }
}

518. 零钱兑换 II⁍

计算并返回可以凑成总金额的硬币组合数。如果任何硬币组合都无法凑出总金额，返回 0 。

思路： 完全背包的组合问题

1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
    public int change(int amount, int[] coins) {
        int[] dp = new int[amount+1];
        dp[0] = 1;
        for (int coin : coins) {
            for (int i = coin; i <= amount ; i++) {
                dp[i] += dp[i-coin];
            }
        }
        return dp[amount];
    }
}

377. 组合总和 Ⅳ⁍

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

题目数据保证答案符合 32 位整数范围。

示例 1：

1
2
3
4
5
6
7
8
9
10
11
12
输入：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)
请注意，顺序不同的序列被视作不同的组合。

示例 2：

1
2
输入：nums = [9], target = 3
输出：0

提示：

  • 1 <= nums.length <= 200
  • 1 <= nums[i] <= 1000
  • nums 中的所有元素 互不相同
  • 1 <= target <= 1000

思路 排列 背包组合问题

dp[i] 和为i的组合个数

dp[i] += dp[i-num]

dp[0] = 1

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
    public int combinationSum4(int[] nums, int target) {
        int[] dp = new int[target+1];
        dp[0] = 1;
        for (int i = 1; i < target+1; i++) {
            for (int num:nums) {
                if (i >= num) {
                    dp[i] += dp[i-num];
                }
            }
        }
        return dp[target];
    }
}

**进阶：**如果给定的数组中含有负数会发生什么？问题会产生何种变化？如果允许负数出现，需要向题目中添加哪些限制条件？

例如，假设数组nums 中含有正整数 a 和负整数−b，则有a×b+(−b)×a=0，对于任意一个元素之和等于target 的排列，在该排列的后面添加 b 个 a 和 a 个 -b之后，得到的新排列的元素之和仍然等于target，而且还可以在新排列的后面继续 b 个 a 和 a 个 −b。因此只要存在元素之和等于 target 的排列，就能构造出无限长度的排列。

如果允许负数出现，则必须限制排列的最大长度，避免出现无限长度的排列，才能计算排列数。

279. 完全平方数⁍

给你一个整数 n ，返回 和为 n 的完全平方数的最少数量 。

完全平方数 是一个整数，其值等于另一个整数的平方；换句话说，其值等于一个整数自乘的积。例如，1、4、9 和 16 都是完全平方数，而 3 和 11 不是。

示例 1：

1
2
3
输入：n = 12
输出：3 
解释：12 = 4 + 4 + 4

思路： 完全背包 最值问题

dp[i] 和为i的完全平方数的最少数量

dp[i] = min(dp[i], dp[i-num]+1)

dp[0] = 0

遍历条件 num^2 <= i

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
    public int numSquares(int n) {
        int[] dp = new int[n+1];
        Arrays.fill(dp,n+1);
        dp[0] = 0;
        for (int i = 1; i <= Math.sqrt(n) ; i++) {
            int num = i*i;
            for (int j = num; j <= n; j++) {
                dp[j] = Math.min(dp[j], dp[j-num]+1);
            }
        }
        return dp[n];
    }
}

1155. 掷骰子的N种方法⁍

这里有 n 个一样的骰子，每个骰子上都有 k 个面，分别标号为 1 到 k 。

给定三个整数 n , k 和 target ，返回可能的方式(从总共 k^n 种方式中)滚动骰子的数量，使正面朝上的数字之和等于 target 。

答案可能很大，你需要对 10^9 + 7 取模 。

示例 1：

1
2
3
4
输入：n = 1, k = 6, target = 3
输出：1
解释：你扔一个有6张脸的骰子。
得到3的和只有一种方法。

示例 2：

1
2
3
4
输入：n = 2, k = 6, target = 7
输出：6
解释：你扔两个骰子，每个骰子有6个面。
得到7的和有6种方法1+6 2+5 3+4 4+3 5+2 6+1。

思路： 分组背包 组合问题外层循环背包组数 i

内层循环 值 和 target，内层 是0/1背包问题

外层 筛子个数 i

第二层 每一面的值 num

第三层 总点数target j

dp[i][j] 前i个骰子总点数为j的不同组合个数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
    private static final int MOD = 1000000007;
    public int numRollsToTarget(int n, int k, int target) {
        int[][] dp = new int[n+1][target+1];
        dp[0][0] = 1;
        for (int i = 1; i <= n; i++) {
            for (int num = 1; num <= k; num++) {
                for (int j = target; j >=num ; j--) {
                    dp[i][j] += dp[i-1][j-num];
                    dp[i][j] %= MOD;
                }
            }
        }
        return dp[n][target];
    }
}
1
2
3
4
5
6
7
8
9
10
11
class Solution:
    def numRollsToTarget(self, n: int, k: int, target: int) -> int:
        dp = [[0]*(target+1)]*(n+1)
        dp[0][0] = 1
        for i in range(1,n+1):
            for num in range(1, k+1):
                for j in range(target,num-1, -1):
                    dp[i][j] += dp[i-1][j-num]
                    dp[i][j] %= 1000000007
            
        return dp[n][target]

关于为什么取模 1e9 + 7：简单来说就是：

取模防止大数运算出现 overflow
为什么取 1e9 + 7 等 prime number 记为 P，可以减少实际答案 A mapping 到 A mod P 的碰撞率。 我们约定认为， 如果你 A mod P 如果是对的，那么你算出的 A 也是对的。还有就是，对于参赛选手来说，这个数好记，不容易出现手误之类的；更详细的 digging 看下面的链接：

作者：maverickbytes
链接：https://leetcode-cn.com/problems/number-of-dice-rolls-with-target-sum/solution/zuo-ti-guo-cheng-ji-lu-dpjie-fa-by-maverickbytes/

  1. 代码随想录 (programmercarl.com) ↩︎ ↩︎

  2. 一篇文章吃透背包问题！（细致引入+解题模板+例题分析+代码呈现） - 最后一块石头的重量 II - 力扣（LeetCode） (leetcode-cn.com) ↩︎ ↩︎