动态规划

背景

120. 三角形最小路径和

给定一个三角形，找出自顶向下的最小路径和。每一步只能移动到下一行中相邻的结点上。

例如，给定三角形：

[
     [2],
    [3,4],
   [6,5,7],
  [4,1,8,3]
]

自顶向下的最小路径和为 11（即，2 + 3 + 5 + 1 = 11）。

DFS

使用 DFS：

// 会超时
public int MinimumTotal(IList<IList<int>> triangle)
{
    return DFS(0, 0, triangle);
}

// 返回值表示从x, y处到底部的最小路径和 
private int DFS(int x, int y, IList<IList<int>> triangle)
{
    if (x == triangle.Count - 1)
    {
        return triangle[x][y];
    }
    int minLeft = DFS(x + 1, y, triangle);
    int minRight = DFS(x + 1, y + 1, triangle);
    return Math.Min(minLeft, minRight) + triangle[x][y];
}

DFS的优化

优化 DFS，缓存已经被计算的值（称为：记忆化搜索 本质上：动态规划）

public int MinimumTotal(IList<IList<int>> triangle)
{
    int[,] saves = new int[triangle.Count, triangle.Count];
    return DFS2(0, 0, triangle, saves);
}

// 使用saves数组记录已经被计算过的值
// 返回值表示从x, y处到底部的最小路径和
private int DFS2(int x, int y, IList<IList<int>> triangle, int[,] saves)
{
    if (x == triangle.Count - 1)
    {
        return triangle[x][y];
    }
    // 如果已经被计算过则直接返回
    if (saves[x, y] != 0)
    {
        return saves[x, y];
    }
    int minLeft = DFS2(x + 1, y, triangle, saves);
    int minRight = DFS2(x + 1, y + 1, triangle, saves);
    // 缓存已经被计算的值
    saves[x, y] = Math.Min(minLeft, minRight) + triangle[x][y];
    return saves[x, y];
}

从DFS到动态规划

动态规划就是把大问题变成小问题，并解决了小问题重复计算的方法称为动态规划

动态规划和 DFS 区别

• 二叉树 子问题是没有交集，所以大部分二叉树都用递归或者分治法，即 DFS，就可以解决

• 像 triangle 这种是有重复走的情况，子问题是有交集，所以可以用动态规划来解决

自底向上

public int MinimumTotal(IList<IList<int>> triangle)
{
    // 1、状态定义：f[i][j] 表示从i,j出发，到达最后一层的最短路径
    int[,] dp = new int[triangle.Count, triangle.Count];
    // 2、初始化
    for (int i = 0; i < triangle.Count; i++)
    {
        dp[triangle.Count - 1, i] = triangle[^1][i];
    }
    // 3、递推求解
    for (int i = triangle.Count - 2; i >= 0; i--)
    {
        for (int j = 0; j < triangle[i].Count; j++)
        {
            dp[i, j] = Math.Min(dp[i + 1, j], dp[i + 1, j + 1]) + triangle[i][j];
        }
    }
    // 4、结果
    return dp[0, 0];
}

自顶向下

public int MinimumTotal(IList<IList<int>> triangle)
{
    // 1、状态定义：dp[i][j] 表示从0,0出发，到达i,j的最短路径
    int[,] dp = new int[triangle.Count, triangle.Count];
    // 2、初始化
    dp[0, 0] = triangle[0][0];
    for (int i = 1; i < triangle.Count; i++)
    {
        for (int j = 0; j < triangle[i].Count; j++)
        {
            // 这里分为三种情况：
            // 1、上一层没有左边值
            // 2、上一层没有右边值
            // 3、其他
            if (j == 0)
            {
                dp[i, j] = dp[i - 1, j] + triangle[i][j];
            }
            else if (j == triangle[i].Count - 1)
            {
                dp[i, j] = dp[i - 1, j - 1] + triangle[i][j];
            }
            else
            {
                dp[i, j] = Math.Min(dp[i - 1, j - 1], dp[i - 1, j]) + triangle[i][j];
            }
        }
    }
    // 从最后一层中查找最小值
    int minValue = dp[triangle.Count - 1, 0];
    for (int i = 0; i < triangle.Count; i++)
    {
        minValue = Math.Min(minValue, dp[triangle.Count - 1, i]);
    }
    return minValue;
}

空间优化

经过观察发现当前状态只与上一批状态有关，所以二维数组可以优化为一位数组，减少空间占用。

public int MinimumTotal(IList<IList<int>> triangle)
{
    int[] dp = new int[triangle.Count];
    for (int i = 0; i < triangle.Count; i++)
    {
        dp[i] = triangle[^1][i];
    }
    for (int i = triangle.Count - 2; i >= 0; i--)
    {
        for (int j = 0; j < triangle[i].Count; j++)
        {
            dp[j] = Math.Min(dp[j], dp[j + 1]) + triangle[i][j];
        }
    }
    return dp[0];
}

除此之外，也可以覆盖原有数据以实现空间复用。

使用场景

满足两个条件

• 满足以下条件之一

  • 求最大/最小值（Maximum/Minimum ）

  • 求是否可行（Yes/No ）

  • 求可行个数（Count(*) ）

• 满足不能排序或者交换（Can not sort / swap ）

如题：longest-consecutive-sequence 位置可以交换，所以不用动态规划

四点要素

1. 状态 State

   • 灵感，创造力，存储小规模问题的结果

2. 方程 Function

   • 状态之间的联系，怎么通过小的状态，来算大的状态

3. 初始化 Intialization

   • 最极限的小状态是什么, 起点

4. 答案 Answer

   • 最大的那个状态是什么，终点

常见四种类型

1. Matrix DP (10%)

2. Sequence (40%)

3. Two Sequences DP (40%)

4. Backpack (10%)

注意点

• 贪心算法大多题目靠背答案，所以如果能用动态规划就尽量用动规，不用贪心算法

矩阵类型

最小路径和

064. 最小路径和

给定一个包含非负整数的 m x n 网格 grid，请找出一条从左上角到右下角的路径，使得路径上的数字总和为最小。

说明：每次只能向下或者向右移动一步。

示例 1：

输入：grid = [[1,3,1],[1,5,1],[4,2,1]]
输出：7
解释：因为路径 1→3→1→1→1 的总和最小。

示例 2：

输入：grid = [[1,2,3],[4,5,6]]
输出：12

public int minPathSum(int[][] grid) {
    // dp[i][j] 表示0,0到i,j的最小和
    int[] dp = new int[grid[0].length];
    // 初始化：用第一行初始化
    dp[0] = grid[0][0];
    for (int i = 1; i < grid[0].length; i++) {
        dp[i] = dp[i-1] + grid[0][i];
    }
    // 状态转移方程
    // 每行第一个元素：
    // dp[j] = dp[j](到上一行这个位置的最小和) + grid[i][j];
    // 后续元素：
    // dp[j] = Math.min(dp[j-1](到左边位置的最小和), dp[j](到上一行这个位置的最小和)) + grid[i][j];
    for (int i = 1; i < grid.length; i++) {
        for (int j = 0; j < grid[0].length; j++) {
            if (j == 0) {
                dp[j] = dp[j] + grid[i][j];
            } else {
                dp[j] = Math.min(dp[j-1], dp[j]) + grid[i][j];
            }
        }
    }
    // 答案
    return dp[grid[0].length - 1];
}

不同路径

062. 不同路径

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

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

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

示例 1：

输入：m = 3, n = 7
输出：28

示例 2：

输入：m = 3, n = 2
输出：3
解释：
从左上角开始，总共有 3 条路径可以到达右下角。
1. 向右 -> 向下 -> 向下
2. 向下 -> 向下 -> 向右
3. 向下 -> 向右 -> 向下

public int UniquePaths(int m, int n)
{
    // dp[i][j] 表示0,0到i,j的路径数
    int[] dp = new int[n];
    // 初始化：到达第一行的路径数均为1
    for (int i = 0; i < n; i++)
    {
        dp[i] = 1;
    }
    for (int i = 1; i < m; i++)
    {
        for (int j = 0; j < n; j++)
        {
            // 每行第一个格子只有一条路到达
            if (j == 0)
            {
                dp[j] = 1;
            }
            // 其他格子可以由左侧或上方的格子到达
            else
            {
                dp[j] = dp[j - 1] + dp[j];
            }
        }
    }
    return dp[n - 1];
}

不同路径 II

063. 不同路径 II

一个机器人位于一个 m x n 网格的左上角 （起始点在下图中标记为“Start” ）。 机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为“Finish”）。

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

现在考虑网格中有障碍物。那么从左上角到右下角将会有多少条不同的路径？

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

示例 1：

输入：obstacleGrid = [[0,0,0],[0,1,0],[0,0,0]]

输出：2

解释： 3x3 网格的正中间有一个障碍物。 从左上角到右下角一共有 2 条不同的路径：

1. 向右 -> 向右 -> 向下 -> 向下

2. 向下 -> 向下 -> 向右 -> 向右

示例 2：

输入：obstacleGrid = [[0,1],[0,0]]

输出：1

public int UniquePathsWithObstacles(int[][] obstacleGrid
{
    int m = obstacleGrid.Length;
    int n = obstacleGrid[0].Length;
    int[] dp = new int[n];
    // 初始化：遇到障碍前仅有一条路，之后全为0
    dp[0] = obstacleGrid[0][0] == 1 ? 0 : 1;
    for (int i = 1; i < n; i++)
    {
        if (obstacleGrid[0][i] == 1)
        {
            dp[i] = 0;
        }
        else
        {
            dp[i] = dp[i - 1];
        }
    }
    for (int i = 1; i < m; i++)
    {
        for (int j = 0; j < n; j++)
        {
            // 当前格是障碍，不可达，置为0
            if (obstacleGrid[i][j] == 1)
            {
                dp[j] = 0;
                continue;
            }
            if (j > 0)
            {
                dp[j] = dp[j - 1] + dp[j];
            }
        }
    }
    return dp[n - 1];
}

序列类型

爬楼梯

070. 爬楼梯

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

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

public int ClimbStairs(int n)
{
    int[] dp = new int[] { 0, 1 };
    while (n > 0)
    {
        int temp = dp[0] + dp[1];
        dp[0] = dp[1];
        dp[1] = temp;
        n--;
    }
    return dp[1];
}

跳跃游戏

055. 跳跃游戏

给你一个非负整数数组 nums，你最初位于数组的 第一个下标 。数组中的每个元素代表你在该位置可以跳跃的最大长度。

判断你是否能够到达最后一个下标，如果可以，返回 true ；否则，返回 false 。

public bool CanJump(int[] nums)
{
    int n = nums.Length;
    int[] dp = new int[n];
    dp[0] = nums[0];
    for (int i = 1; i < n && dp[i] < n - 1; i++)
    {
        if (dp[i - 1] < i)
        {
            return false;
        }
        dp[i] = Math.Max(dp[i - 1], i + nums[i]);
    }
    return true;
}

跳跃游戏-ii

045. 跳跃游戏-ii

给定一个长度为 n 的 0 索引整数数组 nums。初始位置为 nums[0]。

每个元素 nums[i] 表示从索引 i 向前跳转的最大长度。换句话说，如果你在 nums[i] 处，你可以跳转到任意 nums[i + j] 处:

0 <= j <= nums[i] i + j < n 返回到达 nums[n - 1] 的最小跳跃次数。生成的测试用例可以到达 nums[n - 1]。

v1 动态规划

public int Jump(int[] nums)
{
    int n = nums.Length;
    int[] dp = new int[n];
    int prev = 0;
    for (int i = 1; i < n; i++)
    {
        while (prev + nums[prev] < i)
        {
            prev++;
        }
        dp[i] = dp[prev] + 1;
    }
    return dp[n - 1];
}

v2 动态规划+贪心算法

public int Jump_Greedy(int[] nums)
{
    int currJumps = 0; // 当前跳跃次数
    int currMaxPosition = 0; // 跳跃次数 currJumps 可以到达的最大下标
    int nextMaxPosition = 0; // 跳跃次数 currJumps+1 可以到达的最大下标
    int n = nums.Length;
    for (int i = 0; i < n && currMaxPosition < n - 1; i++)
    {
        if (i > currMaxPosition)
        {
            currJumps++;
            currMaxPosition = nextMaxPosition;
        }
        nextMaxPosition = Math.Max(nextMaxPosition, i + nums[i]);
    }
    return currJumps;
}

分割回文串-ii

132. 分割回文串-ii

给你一个字符串 s，请你将 s 分割成一些子串，使每个子串都是回文。

返回符合要求的 最少分割次数。

public int MinCut(string s)
{
    int n = s.Length;
    bool[][] isPalindrome = new bool[n][];
    for (int i = 0; i < n; i++)
    {
        isPalindrome[i] = new bool[n];
        isPalindrome[i][i] = true;
    }
    for (int i = 0; i < n - 1; i++)
    {
        isPalindrome[i][i + 1] = s[i] == s[i + 1];
    }
    for (int subLength = 3; subLength <= n; subLength++)
    {
        for (int i = 0, j = subLength - 1; j < n; i++, j++)
        {
            isPalindrome[i][j] = s[i] == s[j] && isPalindrome[i + 1][j - 1];
        }
    }
    int[] dp = new int[n];
    for (int i = 1; i < n; i++)
    {
        dp[i] = i;
        for (int j = 0; j <= i; j++)
        {
            if (isPalindrome[j][i])
            {
                int currCuts = j == 0 ? 0 : dp[j - 1] + 1;
                dp[i] = Math.Min(dp[i], currCuts);
            }
        }
    }
    return dp[n - 1];
}

注意点

• 判断回文字符串时，可以提前用动态规划算好，减少时间复杂度

最长递增子序列

300. 最长递增子序列

给你一个整数数组 nums ，找到其中最长严格递增子序列的长度。

子序列 是由数组派生而来的序列，删除（或不删除）数组中的元素而不改变其余元素的顺序。例如，[3,6,2,7] 是数组 [0,3,1,6,2,2,7] 的子序列。

public int LengthOfLIS(int[] nums)
{
    // dp[i]表示从0到i的最长上升子序列长度
    int[] dp = new int[nums.Length];
    // 初始化：到第一个元素序列长度为1
    dp[0] = 1;
    for (int i = 1; i < nums.Length; i++)
    {
        // 注意默认为1，即此处最长子序列为自身
        int maxLen = 1;
        // dp[i] = max(dp[j]) + 1 , nums[j] < nums[i]
        for (int j = 0; j < i; j++)
        {
            if (nums[j] < nums[i])
            {
                maxLen = Math.Max(maxLen, dp[j] + 1);
            }
        }
        dp[i] = maxLen;
    }
    int maxNum = 0;
    foreach (var n in dp)
    {
        maxNum = Math.Max(maxNum, n);
    }
    // 答案：dp中的最大值
    return maxNum;
}

单词拆分

139. 单词拆分

给你一个字符串 s 和一个字符串列表 wordDict 作为字典。请你判断是否可以利用字典中出现的单词拼接出 s。

注意：不要求字典中出现的单词全部都使用，并且字典中的单词可以重复使用。

示例 1：

输入: s = "leetcode", wordDict = ["leet", "code"]

输出: true

解释: 返回 true 因为 "leetcode" 可以由 "leet" 和 "code" 拼接成。

示例 2：

输入: s = "applepenapple", wordDict = ["apple", "pen"]

输出: true

解释: 返回 true 因为 "applepenapple" 可以由 "apple" "pen" "apple" 拼接成。

示例 3：

输入: s = "catsandog", wordDict = ["cats", "dog", "sand", "and", "cat"]

输出: false

public bool WordBreak(string s, IList<string> wordDict)
{
    ISet<string> wordDictSet = new HashSet<string>(wordDict);
    int maxWordLength = 0;
    foreach (string word in wordDict)
    {
        maxWordLength = Math.Max(maxWordLength, word.Length);
    }
    int n = s.Length;
    bool[] dp = new bool[n + 1];
    dp[0] = true;
    for (int i = 1; i <= n; i++)
    {
        for (int j = Math.Min(i, maxWordLength); j > 0 && !dp[i]; j--)
        {
            if (dp[i - j] && wordDictSet.Contains(s.Substring(i - j, j)))
            {
                dp[i] = true;
            }
        }
    }
    return dp[n];
}

小结

常见处理方式是给 0 位置占位，这样处理问题时一视同仁，初始化则在原来基础上 length+1，返回结果 f[n]

• 状态可以为前 i 个

• 初始化 length+1

• 取值 index=i-1

• 返回值：f[n]或者 f[m][n]

双序列类型

最长公共子序列

1143. 最长公共子序列

给定两个字符串 text1 和 text2，返回这两个字符串的最长 公共子序列 的长度。如果不存在 公共子序列，返回 0。

一个字符串的 子序列 是指这样一个新的字符串：它是由原字符串在不改变字符的相对顺序的情况下删除某些字符（也可以不删除任何字符）后组成的新字符串。 例如，"ace" 是 "abcde" 的子序列，但 "aec" 不是 "abcde" 的子序列。

两个字符串的 公共子序列 是这两个字符串所共同拥有的子序列。

public int LongestCommonSubsequence(string text1, string text2)
{
    int m = text1.Length;
    int n = text2.Length;
    // dp[i][j] a前i个和b前j个字符最长公共子序列
    // dp[m+1][n+1]
    //   ' a d c e
    // ' 0 0 0 0 0
    // a 0 1 1 1 1
    // c 0 1 1 2 1
    int[][] dp = new int[m + 1][];
    for (int i = 0; i < m + 1; i++)
    {
        dp[i] = new int[n + 1];
    }
    for (int i = 1; i <= m; i++)
    {
        char c1 = text1[i - 1];
        for (int j = 1; j <= n; j++)
        {
            char c2 = text2[j - 1];
            // 相等取左上元素+1，否则取左或上的较大值
            if (c1 == c2)
            {
                dp[i][j] = dp[i - 1][j - 1] + 1;
            }
            else
            {
                dp[i][j] = Math.Max(dp[i - 1][j], dp[i][j - 1]);
            }
        }
    }
    return dp[m][n];
}

注意点

• 从 1 开始遍历到最大长度

• 索引需要减一

编辑距离

072. 编辑距离

给你两个单词 word1 和 word2，请你计算出将 word1 转换成 word2 所使用的最少操作数 。你可以对一个单词进行如下三种操作：

1. 插入一个字符

2. 删除一个字符

3. 替换一个字符

思路：和上题很类似，相等则不需要操作，否则取删除、插入、替换最小操作次数的值+1

public int MinDistance(string word1, string word2)
{
    // dp[i][j] 表示a字符串的前i个字符编辑为b字符串的前j个字符最少需要多少次操作
    // dp[i][j] = OR(dp[i-1][j-1]，a[i]==b[j],min(dp[i-1][j],dp[i][j-1],dp[i-1][j-1])+1)
    int m = word1.Length, n = word2.Length;
    int[][] dp = new int[m + 1][];
    for (int i = 0; i <= m; i++)
    {
        dp[i] = new int[n + 1];
    }
    for (int j = 1; j <= n; j++)
    {
        dp[0][j] = j;
    }
    for (int i = 1; i <= m; i++)
    {
        dp[i][0] = i;
    }
    for (int i = 1; i <= m; i++)
    {
        char c1 = word1[i - 1];
        for (int j = 1; j <= n; j++)
        {
            char c2 = word2[j - 1];
            // 相等则不需要操作
            if (c1 == c2)
            {
                dp[i][j] = dp[i - 1][j - 1];
            }
            // 否则取删除、插入、替换最小操作次数的值+1
            else
            {
                dp[i][j] = Math.Min(Math.Min(dp[i - 1][j], dp[i][j - 1]), dp[i - 1][j - 1]) + 1;
            }
        }
    }
    return dp[m][n];
}

说明

另外一种做法：MAXLEN(a,b)-LCS(a,b)

零钱和背包

零钱兑换

322. 零钱兑换

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

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

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

思路：和其他 DP 不太一样，i 表示钱或者容量

public int CoinChange(int[] coins, int amount)
{
    int n = coins.Length;
    int[][] dp = new int[n + 1][];
    for (int i = 0; i <= n; i++)
    {
        dp[i] = new int[amount + 1];
    }
    Array.Fill(dp[0], INFINITY);
    dp[0][0] = 0;
    for (int i = 1; i <= n; i++)
    {
        for (int j = 0; j <= amount; j++)
        {
            int minCoins = INFINITY;
            int maxCount = j / coins[i - 1];
            for (int k = 0; k <= maxCount; k++)
            {
                minCoins = Math.Min(minCoins, dp[i - 1][j - coins[i - 1] * k] + k);
            }
            dp[i][j] = minCoins;
        }
    }
    return dp[n][amount] != INFINITY ? dp[n][amount] : -1;
}

零钱兑换 ii

518. 零钱兑换 ii

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

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

假设每一种面额的硬币有无限个。

题目数据保证结果符合 32 位带符号整数。

public int Change(int amount, int[] coins)
{
    int n = coins.Length;
    int[][] dp = new int[n + 1][];
    for (int i = 0; i <= n; i++)
    {
        dp[i] = new int[amount + 1];
    }
    dp[0][0] = 1;
    for (int i = 1; i <= n; i++)
    {
        for (int j = 0; j <= amount; j++)
        {
            int maxCount = j / coins[i - 1];
            for (int k = 0; k <= maxCount; k++)
            {
                dp[i][j] += dp[i - 1][j - coins[i - 1] * k];
            }
        }
    }
    return dp[n][amount];
}

背包问题

092. 背包问题

在 n 个物品中挑选若干物品装入背包，最多能装多满？假设背包的大小为 m，每个物品的大小为 Ai

（每个物品只能选择一次且物品大小均为正整数）

public int BackPack(int m, int[] a)
{
    int n = a.Length;
    int[][] dp = new int[n + 1][];
    for (int i = 0; i <= n; i++)
    {
        dp[i] = new int[m + 1];
    }
    for (int i = 1; i <= n; i++)
    {
        for (int j = 0; j <= m; j++)
        {
            dp[i][j] = dp[i - 1][j];
            if (j >= a[i - 1])
            {
                dp[i][j] = Math.Max(dp[i][j], dp[i - 1][j - a[i - 1]] + a[i - 1]);
            }
        }
    }
    return dp[n][m];
}

背包问题-ii

125. 背包问题-ii

有 n 个物品和一个大小为 m 的背包. 给定数组 A 表示每个物品的大小和数组 V 表示每个物品的价值.

问最多能装入背包的总价值是多大?

思路：f[i][j] 前 i 个物品，装入 j 背包 最大价值

public int BackPackII(int m, int[] a, int[] v)
{
    int n = a.Length;
    int[][] dp = new int[n + 1][];
    for (int i = 0; i <= n; i++)
    {
        dp[i] = new int[m + 1];
    }
    for (int i = 1; i <= n; i++)
    {
        for (int j = 0; j <= m; j++)
        {
            dp[i][j] = dp[i - 1][j];
            if (j >= a[i - 1])
            {
                dp[i][j] = Math.Max(dp[i][j], dp[i - 1][j - a[i - 1]] + v[i - 1]);
            }
        }
    }
    return dp[n][m];
}

分割等和子集

416. 分割等和子集

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

等价于0-1背包问题，只不过目标为数组和的一半。状态转移可以参考题解：动态规划（转换为 0-1 背包问题）。

public bool CanPartition(int[] nums)
{
    int len = nums.Length;
    // 题目已经说非空数组，可以不做非空判断
    int sum = 0;
    foreach (int num in nums)
    {
        sum += num;
    }
    // 特判：如果是奇数，就不符合要求
    if ((sum & 1) == 1)
    {
        return false;
    }
    int target = sum / 2;
    // 创建二维状态数组，行：物品索引，列：容量（包括 0）
    bool[][] dp = new bool[len][];
    for (int i = 0; i < len; i++)
    {
        dp[i] = new bool[target + 1];
    }
    // 先填表格第 0 行，第 1 个数只能让容积为它自己的背包恰好装满
    if (nums[0] <= target)
    {
        dp[0][nums[0]] = true;
    }
    // 再填表格后面几行
    for (int i = 1; i < len; i++)
    {
        for (int j = 0; j <= target; j++)
        {
            // 直接从上一行先把结果抄下来，然后再修正
            dp[i][j] = dp[i - 1][j];
            if (nums[i] == j)
            {
                dp[i][j] = true;
                continue;
            }
            if (nums[i] < j)
            {
                dp[i][j] = dp[i - 1][j] || dp[i - 1][j - nums[i]];
            }
        }
    }
    return dp[len - 1][target];
}

练习

Matrix DP (10%)

• 120. 三角形最小路径和

• 064. 最小路径和

• 062. 不同路径

• 063. 不同路径-ii

Sequence (40%)

• 070. 爬楼梯

• 055. 跳跃游戏

• 045. 跳跃游戏-ii

• 132. 分割回文串-ii

• 300. 最长递增子序列

• 139. 单词拆分

Two Sequences DP (40%)

• 1143. 最长公共子序列

• 072. 编辑距离

Backpack & Coin Change (10%)

• 322. 零钱兑换

• 518. 零钱兑换 ii

• 092. 背包问题

• 125. 背包问题-ii

• 416. 分割等和子集