# LeetCode 10. 正则表达式匹配

10. Regular Expression Matching

给你一个字符串 s 和一个字符规律 p ，请你来实现一个支持 '.' 和 '*' 的正则表达式匹配。

• '.' 匹配任意单个字符
• '*' 匹配零个或多个前面的那一个元素

所谓匹配，是要涵盖 整个 字符串 s 的，而不是部分字符串。

示例 1：

输入：s = "aa", p = "a"
输出：false
解释："a" 无法匹配 "aa" 整个字符串。

示例 2：

输入：s = "aa", p = "a*"
输出：true
解释：因为 '*' 代表可以匹配零个或多个前面的那一个元素, 在这里前面的元素就是 'a'。因此，字符串 "aa" 可被视为 'a' 重复了一次。

示例 3：

输入：s = "ab", p = ".*"
输出：true
解释：".*" 表示可匹配零个或多个（'*'）任意字符（'.'）。

提示：

• $1 \le$ s.length $\le 20$
• $1 \le$ p.length $\le 30$
• s 只包含小写字母
• p 只包含小写字母，以及 '.' 和 '*'
• 保证每次出现字符 '*' 时，前面都匹配到有效的字符

# Method: 动态规划

算法思路：

定义 dp 数组 ： dp[i][j] 表示 s[0, i - 1] 是否与 p[0, j - 1] 匹配

初始化 dp 数组： dp[0][0] = true ，其余全部初始化为 false

当字符串 p 以 ".*" 起始时，应有 dp[0][2] = true ，因为 ".*" 可以匹配零个（ '*' ）任意字符（ '.' ）

推导 dp[i][j] 的状态转移过程：

• 当 p[j - 1] == '*' 时，可以考虑将 p[j - 2] 与字符串 s 匹配任意次
  • 若 p[j - 2] == s[i - 1] || p[j - 2] == '.' ，则可以将 p[j - 2] 与 s[i - 1] 进行匹配。由于 p[j - 2] + '*' 这一组合可以匹配零次或多次，我们可以做以下考虑
    • 将其与 s[i - 1] 匹配、并考虑将其与 s[i - 2] 继续匹配（即，将 s[i - 1] 舍弃），此时， dp[i][j] = dp[i - 1][j]
    • 不与 s[i - 1] 匹配，将 p[j - 2] + '*' 这一组合直接舍弃，此时， dp[i][j] = dp[i][j - 2]
    • 综合两种情况可得， dp[i][j] = dp[i - 1][j] || dp[i][j - 2]
  • 若 p[j - 2] != s[i - 1] && p[j - 2] != '.' ，则无法将 p[j - 2] + '*' 这一组合与 s[i - 1] 匹配，应舍弃这一组合，即， dp[i][j] = dp[i][j - 2]
• 当 p[j - 1] != '*' 时，考虑将 p[j - 1] 与 s[i - 1] 匹配
  • 若 p[j - 1] == '.' || s[i - 1] == p[j - 1] ，则可以将 p[j - 1] 与 s[i - 1] 匹配，因此， dp[i][j] = dp[i - 1][j - 1]
  • 若 p[j - 1] != '.' && s[i - 1] != p[j - 1] ，无法将 p[j - 1] 与 s[i - 1] 匹配，此时， dp[i][j] = false

确定遍历顺序：由递推公式知， dp[i][j] 依赖于 dp[i][j - 2] 、 dp[i - 1][j] 以及 dp[i - 1][j - 1] ，因此，应按照从小到大的顺序遍历 i 、按照从小到大的顺序遍历 j

特别地， i 应从 0 开始遍历，这是为了让 s = "" 与 p = ".*" 匹配，即，针对 示例 3 ，有 dp[0][2] = true （因为当 i = 0 、 j = 2 时，会执行 dp[i][j] = dp[i][j - 2] ），进一步地，才能推出 dp[1][2] = true 以及 dp[2][2] = true （因为会执行 dp[i][j] = dp[i][j - 2] || dp[i - 1][j] ）

代码实现：

bool isMatch(string s, string p) {
    vector<vector<bool>> dp(s.size() + 1, vector<bool>(p.size() + 1, false));
    dp[0][0] = true;
    for (int i = 0; i <= s.size(); i++) {
        for (int j = 1; j <= p.size(); j++) {
            if (p[j - 1] == '*') {
                if (i > 0 && (p[j - 2] == '.' || s[i - 1] == p[j - 2]))
                    dp[i][j] = dp[i][j - 2] || dp[i - 1][j];
                else
                    dp[i][j] = dp[i][j - 2];
            } else {
                if (i > 0 && (p[j - 1] == '.' || s[i - 1] == p[j - 1]))
                    dp[i][j] = dp[i - 1][j - 1];
            }
        }
    }
    return dp[s.size()][p.size()];
}

其中，对情况 p[j - 1] == '*' 的处理，即

if (i > 0 && (p[j - 2] == '.' || s[i - 1] == p[j - 2]))
    dp[i][j] = dp[i][j - 2] || dp[i - 1][j];
else
    dp[i][j] = dp[i][j - 2];

可改写为

dp[i][j] = dp[i][j - 2];
if (i > 0 && (p[j - 2] == '.' || s[i - 1] == p[j - 2]))
    dp[i][j] = dp[i][j] || dp[i - 1][j];

时间复杂度：$O(m \times n)$，其中，$m$ 和 $n$ 分别是字符串 s 和 p 的长度

空间复杂度：$O(m \times n)$

参考：力扣官方题解

# LeetCode 1035. 不相交的线

1035. Uncrossed Lines

在两条独立的水平线上按给定的顺序写下 nums1 和 nums2 中的整数。

现在，可以绘制一些连接两个数字 nums1[i] 和 nums2[j] 的直线，这些直线需要同时满足满足：

• nums1[i] == nums2[j]
• 且绘制的直线不与任何其他连线（非水平线）相交。

请注意，连线即使在端点也不能相交：每个数字只能属于一条连线。

以这种方法绘制线条，并返回可以绘制的最大连线数。

示例 1：

输入：nums1 = [1,4,2], nums2 = [1,2,4]
输出：2
解释：可以画出两条不交叉的线，如上图所示。但无法画出第三条不相交的直线，因为从 nums1[1]=4 到 nums2[2]=4 的直线将与从 nums1[2]=2 到 nums2[1]=2 的直线相交

示例 2：

输入：nums1 = [2,5,1,2,5], nums2 = [10,5,2,1,5,2]
输出：3

示例 3：

输入：nums1 = [1,3,7,1,7,5], nums2 = [1,9,2,5,1]
输出：2

提示：

• $1 \le$ nums1.length , nums2.length $\le 500$
• $1 \le$ nums1[i] , nums2[j] $\le 2000$

# 思路

本质是求两个数组的最长公共子序列的长度，即，与 LeetCode 1143. 最长公共子序列 完全一致

# Method: 动态规划

定义 dp[i][j] 表示 nums1[0, i - 1] 与子串 nums2[0, j - 1] 的最长公共子序列的长度，其中， 1 <= i <= nums1.size() , 1 <= j <= nums2.size()

代码实现：

int maxUncrossedLines(vector<int>& nums1, vector<int>& nums2) {
    int m = nums1.size();
    int n = nums2.size();
    vector<vector<int>> dp(m + 1, vector<int>(n + 1, 0));
    for (int i = 1; i <= m; i++) {
        for (int j = 1; j <= n; j++) {
            if (nums1[i - 1] == nums2[j - 1])
                dp[i][j] = dp[i - 1][j - 1] + 1;
            else
                dp[i][j] = max(dp[i][j - 1], dp[i - 1][j]);
        }
    }
    return dp[m][n];
}

时间复杂度：$O(m \times n)$，其中 $m$ 和 $n$ 分别是数组 nums1 与数组 nums2 的长度

空间复杂度：$O(m \times n)$

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

1049. Last Stone Weight II

有一堆石头，用整数数组 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 \le$ stones.length $\le 30$
• $1 \le$ stones[i] $\le 100$

# 思路

本题要求最后剩余的石头重量尽可能小，也就相当于，尽可能将石头分成重量相同的两堆，以使得相撞之后剩下的石头最小

因此，本题类似于 LeetCode 416. 分割等和子集 ，可按照 0-1 背包问题来求解

即，物品 i 的重量为 stones[i] ，价值为 stones[i] ，对于最大容量为 target 的背包，选出若干物品，使背包中的物品总价值最大，其中， target 是 stones 数组元素和的一半

# Method: 动态规划

算法思路：

首先应计算整个数组的元素之和 sum ，并进一步计算背包的最大容量，即， target = sum / 2

然后利用动态规划算法，得到容量为 target 的背包所能实现的最大重量

1. 定义 dp 数组：对于容量为 j 的背包，其物品最大价值为 dp[j] ，其中， 0 <= j < = target

2. 确定递推公式：当 stones[i] <= j <= target 时， dp[j] = max(dp[j], dp[j - stones[i]] + stones[i])

   • 若 j < stones[i] ，即，背包放不下物品 i ，此时， i 不可能被选取， dp[j] 保持不变
   • 若 stones[i] <= j <= target ，可以选择物品 i （最大价值为 dp[j - stones[i]] + stones[i] ），也可以不选物品 i （最大价值为 dp[j] ），综合所得的最大价值为 max(dp[j], dp[j - stones[i]] + stones[i])

3. 初始化 dp 数组：对任意 j ，初始的 dp[j] 均为 0

4. 确定遍历顺序：

   • 外层遍历物品 i ，内层遍历背包容量 j
   • i 按从小到大顺序遍历， j 按从大到小顺序遍历

5. 举例推导 dp 数组

当遍历结束时， dp[target] 即为 最大容量为 target 的背包所能实现的最大重量

此时，一堆石头的重量为 dp[target] ，另一堆的重量为 sum - dp[target]

由于 target = sum / 2 是向下取整，即， dp[target] <= target <= sum / 2 ，故而 dp[target] <= sum - dp[target]

因此，相撞之后，剩余石头的最小重量为 (sum - dp[target]) - dp[target]

代码实现：

int lastStoneWeightII(vector<int>& stones) {
    
    // 计算背包最大容量
    int n = stones.size();
    int sum = 0;
    for (int a : stones) sum += a;
    int target = sum / 2;
    
    // 0-1 背包
    vector<int> dp(target + 1, 0);
    for (int i = 0; i < n; i++) {
        for (int j = target; j >= stones[i]; j--) {
            dp[j] = max(dp[j], dp[j - stones[i]] + stones[i]);
        }
    }

    return (sum - dp[target]) - dp[target];

}

时间复杂度：$O(n \times target)$，其中 $n$ 为数组长度，$target$ 是数组元素和的一半

空间复杂度：$O(target)$

# LeetCode 1143. 最长公共子序列

1143. Longest Common Subsequence

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

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

• 例如， "ace" 是 "abcde" 的子序列，但 "aec" 不是 "abcde" 的子序列。

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

示例 1：

输入：text1 = "abcde", text2 = "ace" 
输出：3  
解释：The longest common subsequence is "ace" and its length is 3.

示例 2：

输入：text1 = "abc", text2 = "abc"
输出：3
解释：The longest common subsequence is "abc" and its length is 3.

示例 3：

输入：text1 = "abc", text2 = "def"
输出：0
解释：There is no such common subsequence, so the result is 0.

提示：

• $1 \le$ text1.length , text2.length $\le 1000$
• text1 和 text2 仅由小写英文字符组成

# Method: 动态规划

算法思路：

dp 数组： dp[i][j] 表示子串 text1[0, i - 1] 与子串 text2[0, j - 1] 的最长公共子序列的长度，其中， 1 <= i <= text1.size() , 1 <= j <= text2.size()

递推公式：

• 若 text1[i - 1] == text2[j - 1] ，则 text1[0, i - 1] 和 text2[0, j - 1] 的最长公共子序列长度 应比 text1[0, i - 2] 和 text2[0, j - 2] 的最长公共子序列长度大 1，即， dp[i][j] = dp[i - 1][j - 1] + 1
• 若 text1[i - 1] != text2[j - 1] ，则做以下考虑：
  • 确定 text1[0, i - 2] 和 text2[0, j - 1] 的最长公共子序列，即，计算 dp[i - 1][j]
  • 确定 text1[0, i - 1] 和 text2[0, j - 2] 的最长公共子序列，即，计算 dp[i][j - 1]
  • 综合两种情况，取最大值，即， dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])

初始化：根据递推公式知，应初始化 dp[0][j] 和 dp[i][0]

• dp[0][j] ：此时考虑的 text1 子串为空串，与 text2 的公共子序列长度为 0 ，即， dp[0][j] = 0
• dp[i][0] ：此时考虑的 text2 子串为空串，与 text1 的公共子序列长度为 0 ，即， dp[i][0] = 0

遍历顺序：外层按从小到大顺序遍历 i ，内层按从小到大顺序遍历 j

遍历结束后， dp[text1.size()][text2.size()] 即为字符串 text1 与字符串 text2 的最长公共子序列的长度

代码实现：

int longestCommonSubsequence(string text1, string text2) {
    int m =text1.size();
    int n =text2.size();
    vector<vector<int>> dp(m + 1, vector<int>(n + 1, 0));
    for (int i = 1; i <= m; i++) {
        for (int j = 1; j <= n; j++) {
            if (text1[i - 1] == text2[j - 1])
                dp[i][j] = dp[i - 1][j - 1] + 1;
            else
                dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
        }
    }
    return dp[m][n];
}

时间复杂度：$O(m \times n)$，其中 $m$ 和 $n$ 分别是字符串 text1 与字符串 text2 的长度

空间复杂度：$O(m \times n)$

参考：代码随想录

# LeetCode 115. 不同的子序列

115. Distinct Subsequences

给你两个字符串 s 和 t ，统计并返回在 s 的 子序列 中 t 出现的个数。

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

示例 1：

输入：s = "rabbbit", t = "rabbit"
输出：3

示例 2：

输入：s = "babgbag", t = "bag"
输出：5

提示：

• $1 \le$ s.length , t.length $\le 1000$
• s 和 t 由英文字母组成

# Method: 动态规划

算法思路：

定义 dp 数组： dp[i][j] 表示在 s[0, i - 1] 中出现 t[0, j - 1] 子序列的个数

初始化 dp[0][j] 和 dp[i][0] ：

• 当 j = 0 时， t[0, j - 1] 为空字符串，由于空字符串是任何字符串的子序列，因此，对任意 0 <= i <= s.size() ，有 dp[i][0] = 1
• 当 i = 0 时， s[0, i - 1] 为空字符串，由于非空字符串不是空字符串的子序列，因此，对任意 1 <= j <= t.size() ，有 dp[0][j] = 0

考虑 dp[i][j] 的状态转移过程：

• 当 s[i - 1] == t[j - 1] 时
  • 如果把 s[i - 1] 与 t[j - 1] 匹配，则需考察 s[0, i - 2] 中出现 t[0, j - 2] 的个数，即， dp[i - 1][j - 1]
  • 如果不把 s[i - 1] 与 t[j - 1] 匹配，则需考察 s[0, i - 2] 中出现 t[0, j - 1] 的个数，即，子序列个数为 dp[i - 1][j]
  • 以上两种情况都是可行的，因此， dp[i][j] = dp[i - 1][j - 1] + dp[i - 1][j]
• 当 s[i - 1] != t[j - 1] 时
  • 无法将 s[i - 1] 与 t[j - 1] 匹配，故而应考察 s[0, i - 2] 中出现 t[0, j - 1] 的个数，即， dp[i][j] = dp[i - 1][j]

例如，当 s = "babgbag" 、t = "bag" 时，$s[0]$ 、$s[2]$ 和 $s[4]$ 都可以与 $t[0]$ 匹配

• 由于 $s[0] = t[0]$ ，有 $dp[1][1] = 1$
• 由于 $s[1] \neq t[0]$ ，有 $dp[2][1] = dp[1][1] = 1$
• 由于 $s[2] = t[0]$ ，有 $dp[3][1] = dp[2][0] + dp[2][1] = 1 + 1 = 2$ ，即，可选 $s[2]$ 与 $t[0]$ 匹配，也可从 $s[0, 1]$ 中选出字符 $s[0]$ 与 $t[0]$ 匹配
• 由于 $s[3] \neq t[0]$ ，有 $dp[4][1] = dp[3][1] = 2$
• 由于 $s[4] = t[0]$ ，有 $dp[4][1] = dp[3][0] + dp[3][1] = 1 + 2 = 3$ ，即，可选 $s[4]$ 与 $t[0]$ 匹配，也可从 $s[0, 3]$ 中选出字符 $s[0]$ 或 $s[2]$ 与 $t[0]$ 匹配

遍历顺序：根据递推公式知， dp[i][j] 依赖于 dp[i - 1][j - 1] 和 dp[i - 1][j] ，因此， i 和 j 都应按从小到大的顺序遍历

代码实现：

int numDistinct(string s, string t) {
    
    // dp 数组的定义及初始化
    vector<vector<uint64_t>> dp(s.size() + 1, vector<uint64_t>(t.size() + 1, 0));
    for (int i = 0; i <= s.size(); i++) dp[i][0] = 1;
    
    // 遍历
    for (int i = 1; i <= s.size(); i++) {
        for (int j = 1; j <= t.size(); j++) {
            if (s[i - 1] == t[j - 1])
                dp[i][j] = dp[i - 1][j - 1] + dp[i - 1][j];
            else
                dp[i][j] = dp[i - 1][j];
        }
    }

    // 返回结果
    return dp[s.size()][t.size()];
    
}

时间复杂度：$O(m \times n)$，其中 $m$ 和 $n$ 分别是字符串 s 和 t 的长度

空间复杂度：$O(m \times n)$

# LeetCode 121. 买卖股票的最佳时机

121. Best Time to Buy and Sell Stock

给定一个数组 prices ，它的第 i 个元素 prices[i] 表示一支给定股票第 i 天的价格。

你只能选择 某一天 买入这只股票，并选择在 未来的某一个不同的日子 卖出该股票。设计一个算法来计算你所能获取的最大利润。

返回你可以从这笔交易中获取的最大利润。如果你不能获取任何利润，返回 0 。

示例 1：

输入：prices = [7,1,5,3,6,4]
输出：5
解释：在第 2 天（股票价格 = 1）的时候买入，在第 5 天（股票价格 = 6）的时候卖出，最大利润 = 6-1 = 5 。注意利润不能是 7-1 = 6, 因为卖出价格需要大于买入价格；同时，你不能在买入前卖出股票。

示例 2：

输入：prices = [7,6,4,3,1]
输出：0
解释：在这种情况下, 没有交易完成, 所以最大利润为 0。

提示：

• $1 \le$ prices.length $\le 10^5$
• $0 \le$ prices[i] $\le 10^4$

# Method 1: 贪心

算法思路：

• 利用 priceBuy 表示买入价，并维护获得的最大利润 maxProfit

• 如果遇到更低的价格，则更新买入价 priceBuy ，后续按新的买入价计算所能得到的利润

代码实现：

int maxProfit(vector<int>& prices) {
    int priceBuy = prices[0]; // 买入价格
    int maxProfit = 0;        // 最大利润
    for (int i = 1; i < prices.size(); i++) {
        priceBuy = min(priceBuy, prices[i]);              
        maxProfit = max(maxProfit, prices[i] - priceBuy);
    }
    return maxProfit;
}

时间复杂度：$O(n)$，其中　$n$ 是数组长度

空间复杂度：$O(1)$

# Method 2: 动态规划

算法思路：

定义 dp 数组： vector<vector<int>> dp(n, vector<int>(2,0))

• dp[i][0] 表示第 i 天持有股票时的最大利润
• dp[i][1] 表示第 i 天不持有股票时的最大利润

确定递推公式：

• 第 i 天持有股票，即， dp[i][0]
  • 若第 i - 1 天持有股票，则最大利润为 dp[i - 1][0]
  • 若第 i - 1 天不持有股票，即，第 i 天买入股票，则最大利润为 - prices[i] （因为只能买入一次股票，第 i - 1 天不持有股票就说明此前并未买入过股票，因此第 i - 1 天的利润必定为 0 ）
  • 综合两种情况得 dp[i][0] = max(dp[i - 1][0], - prices[i]);
• 第 i 天不持有股票，即， dp[i][1]
  • 若第 i - 1 天持有股票，即，第 i 天卖出股票，则最大利润为 dp[i - 1][0] + prices[i]
  • 若第 i - 1 天不持有股票，则最大利润为 dp[i - 1][1]
  • 综合两种情况得 dp[i][1] = max(dp[i - 1][0] + prices[i], dp[i - 1][1])

初始化 dp 数组：

• 若第 0 天持有股票，当前利润应为 - prices[0] ，即 dp[0][0] = - prices[0]
• 若第 0 天不持有股票，利润为 0 ，即 dp[i][1] = 0

遍历顺序：按 i 从小到大遍历

最后的 dp[n - 1][1] 即为所求（卖出股票可以获得收益，因此， dp[n - 1][1] 一定不小于 dp[n - 1][0] ）

代码实现：

int maxProfit(vector<int>& prices) {
    int n = prices.size();
    vector<vector<int>> dp(n, vector<int>(2,0));
    dp[0][0] = - prices[0]; // 第 0 天持有股票时的最大利润
    dp[0][1] = 0;           // 第 0 天不持有股票时的最大利润
    for (int i = 1; i < n; i++) {
        dp[i][0] = max(dp[i - 1][0], - prices[i]);              // 第 i 天持有股票时的最大利润
        dp[i][1] = max(dp[i - 1][0] + prices[i], dp[i - 1][1]); // 第 i 天不持有股票时的最大利润
    }
    return dp[n - 1][1];    // 第 n - 1 天不持有股票时的最大利润
}

时间复杂度：$O(n)$，其中　$n$ 是数组长度

空间复杂度：$O(n)$

参考：代码随想录

# LeetCode 123. 买卖股票的最佳时机 III

123. Best Time to Buy and Sell Stock III

给定一个数组，它的第 i 个元素是一支给定的股票在第 i 天的价格。

设计一个算法来计算你所能获取的最大利润。你最多可以完成 两笔 交易。

注意：你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。

示例 1：

输入：prices = [3,3,5,0,0,3,1,4]
输出：6
解释：在第 4 天（股票价格 = 0）的时候买入，在第 6 天（股票价格 = 3）的时候卖出，这笔交易所能获得利润 = 3-0 = 3 。随后，在第 7 天（股票价格 = 1）的时候买入，在第 8 天 （股票价格 = 4）的时候卖出，这笔交易所能获得利润 = 4-1 = 3 。

示例 2：

输入：prices = [1,2,3,4,5]
输出：4
解释：在第 1 天（股票价格 = 1）的时候买入，在第 5 天 （股票价格 = 5）的时候卖出, 这笔交易所能获得利润 = 5-1 = 4 。

示例 3：

输入：prices = [7,6,4,3,1]
输出：0

提示：

• $1 \le$ prices.length $\le 10^5$
• $0 \le$ prices[i] $\le 10^5$

# Method: 动态规划

算法思路：

定义 dp 数组： dp[i][j] 表示第 i 天状态为 j 时的最大利润

• dp[i][0] ：第 i 天时，未曾买入过股票
• dp[i][1] ：第 i 天时，持有第一支股票（已买入、未卖出，可能第 i 天以前就已买入）
• dp[i][2] ：第 i 天时，不再持有第一支股票（可能是第 i 天以前就已经卖出）
• dp[i][3] ：第 i 天时，持有第二支股票（卖出第一支股票后再次买入，可能第 i 天以前就已买入）
• dp[i][4] ：第 i 天时，不再持有第二支股票（可能是第 i 天以前就已经卖出）

推导递推公式：

• dp[i][0] ：第 i - 1 天必然也不曾买入过股票，故而 dp[i][0] = dp[i - 1][0] （事实上，对任意 i 均有 dp[i][0] = 0 ）
• dp[i][1] ：若第 i - 1 天不曾买入股票，即，第 i 天买入股票，此时利润为 dp[i - 1][0] - prices[i] ；若第 i - 1 天已持有股票，第 i 天时的利润为 dp[i - 1][1] 。综合两种情况，取最大利润，即， dp[i][1] = max(dp[i - 1][0] - prices[i], dp[i - 1][1]) （由于 dp[i - 1][0] = 0 ， dp[i][1] 也可写为 max( - prices[i], dp[i - 1][1]) ）
• dp[i][2] ：若第 i - 1 天不曾卖出股票，即，第 i 天卖出股票，此时利润为 dp[i - 1][1] + prices[i] ；若第 i - 1 天已卖出股票，第 i 天时的利润为 dp[i - 1][2] 。综合两种情况得， dp[i][2] = max(dp[i - 1][1] + prices[i], dp[i - 1][2])
• dp[i][3] ：若第 i - 1 天不曾持有第二支股票，即，第 i 天买入第二支股票，此时利润为 dp[i - 1][2] - prices[i] ；若第 i - 1 天已持有第二支股票，第 i 天时的利润为 dp[i - 1][3] 。综合两种情况得， dp[i][3] = max(dp[i - 1][2] - prices[i], dp[i - 1][3])
• dp[i][4] ：若第 i - 1 天持有第二支股票，即，第 i 天卖出第二支股票，此时利润为 dp[i - 1][3] + prices[i] ；若第 i - 1 天已不再持有第二支股票，第 i 天时的利润为 dp[i - 1][4] 。综合两种情况得， dp[i][4] = max(dp[i - 1][3] + prices[i], dp[i - 1][4])

初始化 dp 数组：

• dp[0][0] = 0 ，第 0 天不进行任何操作，利润为 0
• dp[0][1] = - prices[0] ，第 0 天买入股票，利润为 - prices[0]
• dp[0][2] = 0 ，当天买入股票并当天卖出，利润为 0
• dp[0][3] = - prices[0] ，买入股票，利润为 - prices[0]
• dp[0][4] = 0 ，当天买入股票并当天卖出，利润为 0

遍历顺序：按 i 从小到大顺序遍历

最后的 dp[prices.size() - 1][4] 即为所求

代码实现：

int maxProfit(vector<int>& prices) {
    int n = prices.size();
    vector<vector<int>> dp(n, vector<int>(5, 0));
    dp[0][1] = - prices[0];
    dp[0][3] = - prices[0];
    for (int i = 1; i < n; i++) {
        dp[i][1] = max(dp[i - 1][0] - prices[i], dp[i - 1][1]);
        dp[i][2] = max(dp[i - 1][1] + prices[i], dp[i - 1][2]);
        dp[i][3] = max(dp[i - 1][2] - prices[i], dp[i - 1][3]);
        dp[i][4] = max(dp[i - 1][3] + prices[i], dp[i - 1][4]);
    }
    return dp[n - 1][4];
}

时间复杂度：$O(n)$ ，其中 $n$ 是数组长度

空间复杂度：$O(n)$

可以采用滚动数组优化空间复杂度

参考：代码随想录

# LeetCode 139. 单词拆分

139. Word Break

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

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

示例 1：

输入：s = "leetcode", wordDict = ["leet","code"]
输出：true
解释："leetcode" 可以由 "leet" 和 "code" 拼接成

示例 2：

输入：s = "applepenapple", wordDict = ["apple","pen"]
输出：true
解释："applepenapple" 可以由 "apple" "pen" "apple" 拼接成

示例 3：

输入：s = "catsandog", wordDict = ["cats","dog","sand","and","cat"]
输出：false

提示：

• $1 \le$ s.length $\le 300$
• $1 \le$ wordDict.length $\le 1000$
• $1 \le$ wordDict[i].length $\le 20$
• s 和 wordDict[i] 仅有小写英文字母组成
• wordDict 中的所有字符串 互不相同

# Method: 动态规划

可以把字典 wordDict 中的单词看成物品，把字符串 s 看成背包，要判断 wordDict 中的单词是否能组成字符串 s ，也就是要判断物品是否能装满背包

算法思路：

1. 定义 dp 数组： dp[j] 表示字符串 s 前 j 个字符组成的子串是否能由字典 wordDict 中的单词拼接成，其中， 1 <= j <= s.size()

2. 确定递推公式：对于任意 j ，需要枚举 s[0, ..., j - 1] 中的分割点 i ，看 s[0, ..., i - 1] 组成的字符串（默认 j = 0 时为空串）和 s[i, ..., j - 1] 组成的字符串是否都合法，如果两个字符串都合法，则组成的 s[0, ..., j - 1] 也合法。因此，递推公式为： dp[j] = dp[i] && check(s[i, ..., j - 1]) ，其中， check(s[i, ..., j - 1]) 表示子串 s[i, ..., j - 1] 是否为字典中的单词

3. 初始化 dp 数组：定义 dp[0] = true 表示空串是合法的，对任意 j > 0 均有 dp[j] = false

4. 确定遍历顺序：由于字典 wordDict 中的单词可以重复出现（即，完全背包问题），并且单词出现的顺序并不确定，因此，应该外层 for 循环遍历背包，内层 for 循环遍历物品，其中，内循环须按从小到大顺序遍历

其中，检查子串 s[i, ..., j - 1] 是否为字典中的单词可以通过哈希表实现

代码实现：

bool wordBreak(string s, vector<string>& wordDict) {
    unordered_set<string> hash(wordDict.begin(), wordDict.end());
    vector<bool> dp(s.size() + 1, false); // dp[j] 表示 s[0, j - 1] 是否可由 wordDict 拼接得到
    dp[0] = true;
    for (int j = 1; j <= s.size(); j++) { // 遍历背包
        for (int i = 0; i < j; i++) {     // 遍历物品
            string word = s.substr(i, j - i);               // 截取 s[i, j - 1] 子串
            if (dp[i] && (hash.find(word) != hash.end())) { // s[0, i - 1] 可拼接，s[i, j - 1] 也可拼接
                dp[j] = true;                               // 故而 s[0, j - 1] 可拼接
                break;
            }
        }
    }
    return dp[s.size()];
}

时间复杂度：$O(n^2)$，其中 $n$ 是字符串 s 的长度

空间复杂度：$O(n)$

也可以做一些简单的剪枝，枚举分割点的时候倒着枚举，如果分割点 i 到 j 的长度已经大于字典列表里最长的单词的长度，那么就结束枚举

参考：力扣官方题解

# LeetCode 152. 乘积最大子数组

152. Maximum Product Subarray

给你一个整数数组 nums ，请你找出数组中乘积最大的非空连续子数组（该子数组中至少包含一个数字），并返回该子数组所对应的乘积。

测试用例的答案是一个 32 - 位 整数。

子数组 是数组的连续子序列。

示例 1：

输入：nums = [2,3,-2,4]
输出：6
解释：子数组 [2,3] 有最大乘积 6

示例 2：

输入：nums = [-2,0,-1]
输出：0
解释：结果不能为 2, 因为 [-2,-1] 不是子数组

提示：

• $1 \le$ nums.length $\le 2 \times 10^4$
• $-10 \le$ nums[i] $\le 10$
• nums 的任何前缀或后缀的乘积都 保证 是一个 32 - 位 整数

# Method: 动态规划

算法思路：

由于数组 nums 存在负数，子数组的乘积可能会出现 “最大的正数变成最小的负数”、“ 最小的负数变成最大的正数 ” 这两种情况

因此，我们可以分别定义 maxValue 数组和 minValue 数组

• maxValue [i] 表示以 nums [i] 结尾的乘积最大子数组的乘积
• minValue [i] 表示以 nums [i] 结尾的乘积最小子数组的乘积

代码实现：

int maxProduct(vector<int>& nums) {
    vector<int> maxValue(nums.size(), 0);
    vector<int> minValue(nums.size(), 0);
    int ans = nums[0];
    maxValue[0] = nums[0];
    minValue[0] = nums[0];
    for (int i = 1; i < nums.size(); ++i) {
        maxValue[i] = max({maxValue[i - 1] * nums[i], minValue[i - 1] * nums[i], nums[i]});
        minValue[i] = min({maxValue[i - 1] * nums[i], minValue[i - 1] * nums[i], nums[i]});
        ans = max(ans, maxValue[i]);
    }
    return ans;
}

时间复杂度：$O(n)$，其中 $n$ 是数组的长度

空间复杂度：$O(n)$

可以采用滚动数组的思想来优化空间复杂度

# LeetCode 188. 买卖股票的最佳时机 IV

188. Best Time to Buy and Sell Stock IV

给定一个整数数组 prices ，它的第 i 个元素 prices[i] 是一支给定的股票在第 i 天的价格，和一个整型 k 。

设计一个算法来计算你所能获取的最大利润。你最多可以完成 k 笔交易。也就是说，你最多可以买 k 次，卖 k 次。

注意：你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。

示例 1：

输入：k = 2, prices = [2,4,1]
输出：2
解释：在第 1 天 (股票价格 = 2) 的时候买入，在第 2 天 (股票价格 = 4) 的时候卖出，这笔交易所能获得利润 = 4-2 = 2

示例 2：

输入：k = 2, prices = [3,2,6,5,0,3]
输出：7
解释：在第 2 天 (股票价格 = 2) 的时候买入，在第 3 天 (股票价格 = 6) 的时候卖出, 这笔交易所能获得利润 = 6-2 = 4 。     随后，在第 5 天 (股票价格 = 0) 的时候买入，在第 6 天 (股票价格 = 3) 的时候卖出, 这笔交易所能获得利润 = 3-0 = 3

提示：

• $0 \le$ k $\le 100$
• $0 \le$ prices.length $\le 1000$
• $0 \le$ prices[i] $\le 1000$

# Method: 动态规划

LeetCode 123. 买卖股票的最佳时机 III 允许进行至多 $2$ 次交易，而本题允许进行至多 $k$ 次交易

算法思路：

定义 dp 数组： dp[i][j] 表示第 i 天状态为 j 时的最大利润，其中， 0 <= i <= prices.size() - 1 ， 0 <= j <= 2 * k

• dp[i][0] ：没有任何操作
• dp[i][1] ：持有第 1 支股票
• dp[i][2] ：不再持有第 1 支股票
• ...
• dp[i][2 * k - 1] ：持有第 $k$ 支股票
• dp[i][2 * k] ：不再持有第 $k$ 支股票

不难发现，对于 dp[i][j] 而言， j 为奇数时表示当前持有股票， j 为偶数（ j > 0 ）时表示当前并不持有股票

因此，递推公式为：

• 当 j 为奇数时，有 dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - 1] - prices[i])
• 当 j 为偶数时，有 dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - 1] + prices[i])

并且，dp 数组的初始值应为：

• 当 j 为奇数时， dp[0][j] = - prices[0]
• 当 j 为偶数时， dp[0][j] = 0

代码实现：

int maxProfit(int k, vector<int>& prices) {
    if (prices.size() == 0) return 0;
    if (k == 0) return 0;
    vector<vector<int>> dp(prices.size(), vector<int>(2 * k + 1));
    for (int j = 1; j < 2 * k; j += 2) {
        dp[0][j] = - prices[0];
    }
    for (int i = 1; i < prices.size(); i++) {
        for (int j = 0; j < 2 * k - 1; j += 2) {
            dp[i][j + 1] = max(dp[i - 1][j] - prices[i], dp[i - 1][j + 1]);
            dp[i][j + 2] = max(dp[i - 1][j + 1] + prices[i], dp[i - 1][j + 2]);
        }
    }
    return dp[prices.size() - 1][2 * k];
}

时间复杂度：$O(n \times k)$ ，其中 $n$ 是数组 prices 的长度，$k$ 是允许的交易次数

空间复杂度：$O(n \times k)$

参考：代码随想录

# LeetCode 198. 打家劫舍

198. House Robber

你是一个专业的小偷，计划偷窃沿街的房屋。每间房内都藏有一定的现金，影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。

给定一个代表每个房屋存放金额的非负整数数组，计算你 不触动警报装置的情况下 ，一夜之内能够偷窃到的最高金额。

示例 1：

输入：nums = [1,2,3,1]
输出：4
解释：偷窃 1 号房屋 (金额 = 1) ，然后偷窃 3 号房屋 (金额 = 3)。偷窃到的最高金额 = 1 + 3 = 4

示例 2：

输入：nums = [2,7,9,3,1]
输出：12
解释：偷窃 1 号房屋 (金额 = 2), 偷窃 3 号房屋 (金额 = 9)，接着偷窃 5 号房屋 (金额 = 1)。偷窃到的最高金额 = 2 + 9 + 1 = 12

提示：

• $1 \le$ nums.length $\le 100$
• $0 \le$ nums[i] $\le 400$

# Method: 动态规划

算法思路：

定义 dp 数组：$dp[i]$ 表示从第 $0$ 到第 $i$ 间房屋（即，$[0, i]$ ）能偷窃到的最高总金额

递推公式：当 $i \ge 2$ 时，$dp[i] = max(dp[i - 2] + nums[i], dp[i - 1])$

• 偷窃第 $i$ 间房屋，能达到的最高总金额为 $dp[i - 2] + nums[i]$
• 不偷窃第 $i$ 间房屋，可考虑偷窃第 $i - 1$ 间房屋，能达到的最高总金额为 $dp[i - 1]$
• 综合两种情况，取其中最大的，即，$dp[i] = max(dp[i - 2] + nums[i], dp[i - 1])$

初始化 dp 数组：根据递推公式知，应初始化 $dp[0]$ 和 $dp[1]$

• 当 $i = 0$ 时，能偷窃的最高金额为 $nums[0]$ ，故而 $dp[0] = nums[0]$
• 当 $i = 1$ 时，能偷窃的最高金额为 $max(nums[0], nums[1])$ ，故而 $dp[1] = max(nums[0], nums[1])$

遍历顺序：按从小到大的顺序遍历 $i$

代码实现：

int rob(vector<int>& nums) {
    int n = nums.size();
    if (n == 0) return 0;
    if (n == 1) return nums[0];
    vector<int> dp(n, 0);
    dp[0] = nums[0];
    dp[1] = max(nums[0], nums[1]);
    for (int i = 2; i < n; i++) {
        dp[i] = max(dp[i - 2] + nums[i], dp[i - 1]);
    }
    return dp[n - 1];
}

时间复杂度：$O(n)$，其中 $n$ 是数组长度

空间复杂度：$O(n)$

# LeetCode 203. 移除链表元素

LeetCode 203. Remove Linked List Elements

给你一个链表的头节点 head 和一个整数 val ，请你删除链表中所有满足 Node.val == val 的节点，并返回 新的头节点 。

示例 1：

输入：head = [1,2,6,3,4,5,6], val = 6
输出：[1,2,3,4,5]

示例 2：

输入：head = [], val = 1
输出：[]

示例 3：

输入：head = [7,7,7,7], val = 7
输出：[]

提示：

• 列表中的节点数目在范围 $[0, 10^4]$ 内
• $1 \le$ Node.val $\le 50$
• $0 \le$ val $\le 50$

# 思路

用 cur 表示当前节点：如果 cur 的下一个节点不为空 且 下一个节点的值等于给定的 val ，即， cur->next != NULL && cur->next->val == val ，则需要移除 cur 的下一个节点，即： cur->next = cur->next->next

但如果要移除的节点是头节点（它没有上个节点）怎么办？

• Method 1：直接将头节点向后移动
• Method 2：在头节点前添加一个虚拟节点，使得原链表的所有节点均可按照常规的方式进行移除

# Method 1: 直接使用原链表来进行删除操作

1. 若要移除头节点，只需将头节点向后移动一位

2. 考虑到新的头节点也可能是值为 val ，需要用循环来对头节点进行处理，直到头节点值不为 val

3. 对头节点以后的其他节点进行遍历，若需移除则按常规方式处理即可

代码实现：

struct ListNode {
    int val;
    ListNode *next;
    ListNode() : val(0), next(nullptr) {}
    ListNode(int x) : val(x), next(nullptr) {}
    ListNode(int x, ListNode *next) : val(x), next(next) {}
};

ListNode* removeElements(ListNode* head, int val) {
    // 删除值为 val 的头节点
    while (head != nullptr && head->val == val) {
        ListNode* tmp = head;
        head = head->next;
        delete tmp;
    }

    // 删除值为 val 的非头节点
    ListNode* cur = head;   // 遍历 cur 节点
    while(cur != nullptr && cur->next != nullptr) { // cur 非空且 cur 的下一个节点非空
        if (cur->next->val == val) {    // 当 cur 的下一个节点的值为 val 时，删除 cur 的下一个节点
            ListNode* tmp = cur->next;
            cur->next = cur->next->next;
            delete tmp;
        }
        else
            cur = cur->next;  // cur 向后移动
    }

    // 返回新的头节点
    return head;
}

注意要从内存中删除移除的节点，清理节点内存

# Method 2: 设置虚拟头节点再进行删除操作

设置一个虚拟头结点，原链表的所有节点便都可按照统一的方式进行移除

例如，给链表添加一个虚拟头结点为新的头结点，若要移除这个旧的头结点元素 1 时，只需将虚拟头节点的 next 指向旧的头节点的下一个节点，然后从内存中删除旧的头节点即可：

注意，在 return 头节点 时， return 的应该是虚拟头节点的下一个节点，即， return dummyHead->next;

最后也需要将添加的虚拟头节点 dummyHead 从内存中删掉

代码实现：

struct ListNode {
    int val;
    ListNode *next;
    ListNode() : val(0), next(nullptr) {}
    ListNode(int x) : val(x), next(nullptr) {}
    ListNode(int x, ListNode *next) : val(x), next(next) {}
};

ListNode* removeElements(ListNode* head, int val) {
    // 设置虚拟头节点
    ListNode* dummyHead = new ListNode(0);  // 创建虚拟头节点
    dummyHead->next = head;                 // 令虚拟头节点指向 head

    // 移除操作
    ListNode* cur = dummyHead;
    while (cur->next != nullptr) {
        if (cur->next->val == val) {
            ListNode* tmp = cur->next;
            cur->next = cur->next->next;
            delete tmp;
        }
        else
            cur = cur->next;
    }

    // 返回虚拟头节点的下个节点，并删除虚拟头节点
    head = dummyHead->next;
    delete dummyHead;
    return head;
}

时间复杂度：$O(n)$，其中，$n$ 是链表的长度

空间复杂度：$O(1)$

# LeetCode 213. 打家劫舍 II

213. House Robber II

你是一个专业的小偷，计划偷窃沿街的房屋，每间房内都藏有一定的现金。这个地方所有的房屋都 围成一圈 ，这意味着第一个房屋和最后一个房屋是紧挨着的。同时，相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警 。

给定一个代表每个房屋存放金额的非负整数数组，计算你 在不触动警报装置的情况下 ，今晚能够偷窃到的最高金额。

示例 1：

输入：nums = [2,3,2]
输出：3
解释：只能偷窃 2 号房屋（金额 = 3）。

示例 2：

输入：nums = [1,2,3,1]
输出：4
解释：你可以先偷窃 1 号房屋（金额 = 1），然后偷窃 3 号房屋（金额 = 3）。

示例 3：

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

提示：

• $1 \le$ nums.length $\le 100$
• $0 \le$ nums[i] $\le 1000$

# 思路

与 LeetCode 198. 打家劫舍 有所不同，本题的房屋是首尾相连的，因此，第一间房屋和最后一间房屋不能在同一晚上偷窃

当只有一间房屋时，偷窃的最高金额就是 $nums[0]$

当房屋数量大于等于 2 时，考虑两种情况：

• 可以偷窃第一间房屋、但不可以偷窃最后一间房屋，即，考虑偷窃 $[0, nums.size() - 2]$ 这一区间内的房屋
• 不可以偷窃第一间房屋、但可以偷窃最后一间房屋，即，考虑偷窃 $[1, nums.size() - 1]$ 这一区间内的房屋

其中，每一种情况都可以按照 LeetCode 198. 打家劫舍 中的方法求解

# Method: 动态规划

代码实现：

int robRange(vector<int>& nums, int left, int right) { // 打家劫舍，区间 nums[left, right]
    if (left == right) return nums[left];
    vector<int> dp(nums.size(), 0);
    dp[left] = nums[left];
    dp[left + 1] = max(nums[left], nums[left + 1]);
    for (int i = left + 2; i <= right; i++)
        dp[i] = max(dp[i - 2] + nums[i], dp[i - 1]);
    return dp[right];
}

int rob(vector<int>& nums) {
    if (nums.size() == 1) return nums[0];
    int result1 = robRange(nums, 0, nums.size() - 2); // 不考虑尾元素
    int result2 = robRange(nums, 1, nums.size() - 1); // 不考虑首元素
    return max(result1, result2);
}

时间复杂度：$O(n)$，其中 $n$ 是数组长度

空间复杂度：$O(n)$

# LeetCode 221. 最大正方形

221. Maximal Square

在一个由 '0' 和 '1' 组成的二维矩阵内，找到只包含 '1' 的最大正方形，并返回其面积。

示例 1：

输入：matrix = [["1","0","1","0","0"],["1","0","1","1","1"],["1","1","1","1","1"],["1","0","0","1","0"]]
输出：4

示例 2：

输入：matrix = [["0","1"],["1","0"]]
输出：1

示例 3：

输入：matrix = [["0"]]
输出：0

提示：

• m == matrix.length
• n == matrix[i].length
• 1 <= m, n <= 300
• matrix[i][j] 为 '0' 或 '1'

# Method: 动态规划

算法思路：

定义 dp 数组：dp [i][j] 表示以 (i, j) 为右下角、只包含 '1' 的正方形的最大边长

确定递推公式：

• 如果位置 (i, j) 的值是 '0' ，则 dp [i][j] = 0
• 如果位置 (i, j) 的值是 '1' ，则 dp [i][j] 依赖于其上方、左方和左上方这三个相邻位置的 dp 值，dp [i][j] = min ({dp [i - 1][j - 1], dp [i - 1][j], dp [i][j - 1]}) + 1

需结合具体实例来理解递推公式，其详细证明可参考 力扣官方题解：统计全为 1 的正方形子矩阵

代码实现：

int maximalSquare(vector<vector<char>>& matrix) {
    int m = matrix.size();
    int n = matrix[0].size();
    vector<vector<int>> dp(m, vector<int>(n, 0));
    int sideLength = 0; // 最大边长
    for (int i = 0; i < m; ++i) {
        for (int j = 0; j < n; ++j) {
            if (matrix[i][j] == '1') {
                if (i == 0 || j == 0)
                    dp[i][j] = 1;
                else
                    dp[i][j] = min({dp[i - 1][j - 1], dp[i - 1][j], dp[i][j - 1]}) + 1;
                sideLength = max(sideLength, dp[i][j]);
            }
        }
    }
    int ans = sideLength * sideLength; // 面积
    return ans;
}

时间复杂度：$O(m \times n)$，其中 $m$ 和 $n$ 分别是矩阵的行数和列数

空间复杂度：$O(m \times n)$

参考：leetcode-solution

# LeetCode 27. 移除元素

LeetCode 27. Remove Element

给你一个数组 nums 和一个值 val ，你需要 原地 移除所有数值等于 val 的元素，并返回移除后数组的新长度。

由于在某些语言中无法改变数组的长度，必须让结果放在数组 nums 的最前面。因此，如果在去除重复元素后还有 k 个元素，那么应该将结果放在 nums 的前 k 个位置，并返回 k 。

不要使用额外的数组空间，你必须仅使用 $O(1)$ 额外空间并 原地 修改输入数组。

元素的顺序可以改变。你不需要考虑数组中超出新长度后面的元素。

说明:

为什么返回数值是整数，但输出的答案是数组呢？

请注意，输入数组是以「引用」方式传递的，这意味着在函数里修改输入数组对于调用者是可见的。

你可以想象内部操作如下:

int[] nums = [...]; // Input array
int val = ...;      // Value to remove
int[] expectedNums = [...]; // The expected answer with correct length.
                            // It is sorted with no values equaling val.

int k = removeElement(nums, val); // Calls your implementation

assert k == expectedNums.length;
sort(nums, 0, k);           // Sort the first k elements of nums
for (int i = 0; i < actualLength; i++) {
    assert nums[i] == expectedNums[i];
}

示例 1：

输入：nums = [3,2,2,3], val = 3
输出：2, nums = [2,2,_,_]
解释：函数应该返回新的长度 2, 并且 nums 中的前两个元素均为 2。你不需要考虑数组中超出新长度后面的元素。例如，函数返回的新长度为 2 ，而 nums = [2,2,3,3] 或 nums = [2,2,0,0]，也会被视作正确答案。

示例 2：

输入：nums = [0,1,2,2,3,0,4,2], val = 2
输出：5, nums = [0,1,4,0,3,_,_,_]
解释：函数应该返回新的长度 5, 并且 nums 中的前五个元素为 0, 1, 3, 0, 4。注意这五个元素可为任意顺序。你不需要考虑数组中超出新长度后面的元素。

限制:

• $0 \le$ nums.length $\le 100$
• $0 \le$ nums[i] $\le 50$
• $0 \le$ val $\le 100$

# Method 1: 双指针

slow 对应 将要被覆盖的位置， fast 对应 当前搜索位置，均初始化为 0

fast 右移，并进行如下操作，直到 fast == nums.size() - 1 ：

• 如果 nums[fast] == val ，跳过该元素

• 如果 nums[fast] != val ，令 nums[slow] = nums[fast] ，并让 l 右移一位

代码实现：

int removeElement(vector<int>& nums, int val) {
    int n = nums.size();
    int slow = 0;
    for (int fast = 0; fast < n; fast++)
        if (nums[fast] != val) // 对值不为 val 的元素进行移位，值为 val 则跳过
            nums[slow++] = nums[fast];
    return slow;               // slow 即为 新数组的长度
}

时间复杂度 ：$O(n)$，其中 $n$ 为数组的长度

空间复杂度 ：$O(1)$

# Method 2: 双指针优化

如果要移除的元素恰好在数组的开头，方法一需要把每一个元素都左移一位

可以定义两个指针，初始时分别指向数组的首尾，向中间移动遍历该序列（题目允许改变元素的顺序）

算法流程：

执行以下循环，直到 left 与 right 重合

• 判断 left 的元素是否等于 val
  • 若是，将 right 指向的元素复制到 left 的位置，然后 right 左移一位
  • 若否， left 右移一位

注意这里的 right 指向的元素也有可能是 val ，此时：

• 可以选择将 val 赋值给 left ，然后 right 左移（在这种情况下，赋值后 left 位置的元素仍为 val ， left 不会移动）
• 也可以选择跳过该元素，即， right 直接左移

代码实现：

int removeElement(vector<int>& nums, int val) {
    int left = 0, right = nums.size() - 1;
    while (left < right) {
        if (nums[left] == val)
            nums[left] = nums[right--];
        else
            left++;
    }
    return left;
}

时间复杂度 ：$O(n)$

空间复杂度 ：$O(1)$

与 Method 1 相比，Method 2 避免了值不为 val 元素的重复赋值操作

# LeetCode 279. 完全平方数

279. Perfect Squares

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

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

示例 1：

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

示例 2：

输入：n = 13
输出：2
解释：13 = 4 + 9

提示：

• $1 \le$ n $\le 10^4$

# 思路

可以将完全平方数视为背包问题中的物品，所需凑成的整数 n 即为背包最大容量，求解装满背包所需物品的最小数量

其中，物品可以重复选取，因此，本题是一个完全背包问题

# Method: 动态规划

算法思路：

定义 dp 数组： dp[j] 表示凑成 j 所需完全平方数的最少数量，其中 0 <= j <= n

递推公式：当 j >= i * i 时，可选取 i * i ，也可不选取 i * i ，因此 dp[j] = min(dp[j], 1 + dp[j - i * i])

初始化 dp 数组：如果和为 0 ，最少需要 0 个完全平方数，即 dp[0] = 0 ，为确保递推公式的更新，应将任意 j > 0 的 dp[j] 初始化为一个比较大的数值，例如 INT_MAX

遍历顺序：完全平方数的选取顺序不影响最终结果，可以采用外层遍历物品、内层遍历背包容量，其中，物品、背包容量均需按照从小到大的顺序遍历

代码实现：

int numSquares(int n) {
    vector<int> dp(n + 1, INT_MAX);
    dp[0] = 0;
    for (int i = 1; i * i <= n; i++) { // 遍历物品
        for (int j = 1; j <= n; j++) { // 遍历背包容量
            if (j >= i * i)
                dp[j] = min(dp[j], 1 + dp[j - i * i]);
        }
    }
    return dp[n];
}

或者

int numSquares(int n) {
    vector<int> dp(n + 1, INT_MAX);
    dp[0] = 0;
    for (int j = 1; j <= n; j++) {         // 遍历背包容量
        for (int i = 1; i * i <= j; i++) { // 遍历物品
            dp[j] = min(dp[j], 1 + dp[j - i * i]);
        }
    }
    return dp[n];
}

时间复杂度：$O(n \times \sqrt{n})$

空间复杂度：$O(n)$

# LeetCode 300. 最长递增子序列

300. Longest Increasing Subsequence

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

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

示例 1：

输入：nums = [10,9,2,5,3,7,101,18]
输出：4
解释：最长递增子序列是 [2,3,7,101]，因此长度为 4

示例 2：

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

示例 3：

输入：nums = [7,7,7,7,7,7,7]
输出：1

提示：

• $1 \le$ nums.length $\le 2500$
• $- 10^4 \le$ nums[i] $\le 10^4$

进阶：你能将算法的时间复杂度降低到 $O(n \log{n})$ 吗？

# Method: 动态规划

算法思路：

定义 dp 数组： dp[i] 表示在 [0, i] 区间内，以 nums[i] 结尾的最长递增子序列的长度

确定递推公式：

• 对任意一个满足条件 0 <= j < i && nums[j] < nums[i] 的 nums[j] 而言，可以在 以 nums[j] 结尾的最长递增子序列 之后再添加一个 nums[i] ，形成更长的递增子序列，其中，新的序列长度即为 dp[j] + 1

• 因此，要想得到以 nums[i] 结尾的最长递增子序列，应将 nums[i] 添加在 满足 0 <= j < i && nums[j] < nums[i] 条件、且具有最大 dp[j] 的 nums[j] 之后，即， dp[i] = max(dp[j]) + 1 ，其中 0 <= j < i && nums[j] < nums[i]

初始化 dp 数组：对于任意 i 而言， nums[i] 自身就是一个长度为 1 的递增子序列，因此，任意的 dp[i] 都应初始化为 1

确定遍历顺序：按 i 从小到大的顺序遍历

最后，从所有的 dp[i] 中找出最大值，即为最长递增子序列的长度

代码实现：

int lengthOfLIS(vector<int>& nums) {
    int n = nums.size();
    vector<int> dp(n, 1); // dp[i] 表示以 nums[i] 结尾的最长严格递增子序列的长度
    for (int i = 1; i < n; i++) {
        for (int j = 0; j < i; j++) {
            if (nums[i] > nums[j]) // nums[i] 可以接在 nums[j] 之后，形成新的递增子序列
                dp[i] = max(dp[i], dp[j] + 1);
        }
    }
    int ans = 0; // 最长递增子序列的长度
    for (int i = 0; i < n; i++) {
        ans = max(ans, dp[i]);
    }
    return ans;
}

时间复杂度：$O(n^2)$ ，其中 $n$ 是数组的长度

空间复杂度：$O(n)$

# Method 2: 贪心 + 二分查找

时间复杂度：$O(n \log{n})$

参考：力扣官方题解

# LeetCode 309. 最佳买卖股票时机含冷冻期

309. Best Time to Buy and Sell Stock with Cooldown

给定一个整数数组 prices ，其中第 prices[i] 表示第 i 天的股票价格 。​

设计一个算法计算出最大利润。在满足以下约束条件下，你可以尽可能地完成更多的交易（多次买卖一支股票）:

• 卖出股票后，你无法在第二天买入股票 (即冷冻期为 1 天)。

注意：你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。

示例 1：

输入：prices = [1,2,3,0,2]
输出：3
解释：对应的交易状态为: [买入, 卖出, 冷冻期, 买入, 卖出]

示例 2：

输入：prices = [1]
输出：0

提示：

• $1 \le$ prices.length $\le 5000$
• $0 \le$ prices[i] $\le 1000$

# Method: 动态规划

算法思路：

定义 dp 数组： vector<vector<int>> dp(prices.size(), vector<int>(2,0))

• dp[i][0] 表示第 i 天结束时不持有股票的最大利润
• dp[i][1] 表示第 i 天结束时持有股票的最大利润

确定递推公式：

• 第 i 天结束时不持有股票，即， dp[i][0]
  • 若第 i - 1 天不持有股票，此时的利润为 dp[i - 1][0]
  • 若第 i - 1 天持有股票、第 i 天卖出股票，此时的利润为 dp[i - 1][1] + prices[i]
  • 综合两种情况得 dp[i][0] = max(dp[i - 1][0], dp[i - 1][1] + prices[i]);
• 第 i 天结束时持有股票，即， dp[i][1]
  • 若第 i - 2 天不持有股票、第 i 天买入股票，此时的利润为 dp[i - 2][0] - prices[i] （购买股票具有 1 天的冷冻期，第 i 天买入股票要求第 i - 2 天已经卖出股票）
  • 若第 i - 1 天持有股票，此时利润为 dp[i - 1][1]
  • 综合两种情况得 dp[i][1] = max(dp[i - 1][1], dp[i - 2][0] - prices[i])

初始化 dp 数组：根据递推公式知，应初始化 dp[0][] 和 dp[1][]

• 第 0 天不持有股票：利润为 0 ，即 dp[i][0] = 0
• 第 0 天持有股票：当前利润为 - prices[0] ，即 dp[0][1] = - prices[0]
• 第 1 天不持有股票：若第 0 天不持有股票，则利润为 0 ；若第 0 天持有股票、第 1 天卖出股票，则利润为 prices[1] - prices[0] 。因此， dp[1][0] = max(0, prices[1] - prices[0])
• 第 1 天持有股票：若第 0 天买入股票，则利润为 dp[0][1] ；若第 1 天买入股票，则利润为 - prices[1] 。因此， dp[1][1] = max(dp[0][1], - prices[1])

遍历顺序：按 i 从小到大遍历

最后的 dp[n - 1][0] 即为所求

代码实现：

int maxProfit(vector<int>& prices) {
    int n = prices.size();
    if (n <= 1) return 0;
    vector<vector<int>> dp(n, vector<int>(2, 0));
    dp[0][0] = 0;           // 第 0 天不持有股票时的最大利润
    dp[0][1] = - prices[0]; // 第 0 天持有股票时的最大利润
    dp[1][0] = max(dp[0][1] + prices[1], dp[0][0]);
    dp[1][1] = max(dp[0][0] - prices[1], dp[0][1]);
    for (int i = 2; i < n; i++) {
        dp[i][0] = max(dp[i - 1][0], dp[i - 1][1] + prices[i]);
        dp[i][1] = max(dp[i - 1][1], dp[i - 2][0] - prices[i]); // 具有冷冻期
    }
    return dp[n - 1][0];
}

时间复杂度：$O(n)$ ，其中 $n$ 是数组 prices 的长度

空间复杂度：$O(n)$

# LeetCode 312. 戳气球

312. Burst Balloons

有 n 个气球，编号为 0 到 n - 1，每个气球上都标有一个数字，这些数字存在数组 nums 中。

现在要求你戳破所有的气球。戳破第 i 个气球，你可以获得 nums [i - 1] * nums [i] * nums [i + 1] 枚硬币。 这里的 i - 1 和 i + 1 代表和 i 相邻的两个气球的序号。如果 i - 1 或 i + 1 超出了数组的边界，那么就当它是一个数字为 1 的气球。

求所能获得硬币的最大数量。

示例 1：

输入：nums = [3,1,5,8]
输出：167
解释：
nums = [3,1,5,8] --> [3,5,8] --> [3,8] --> [8] --> []
coins =  3*1*5    +   3*5*8   +  1*3*8  + 1*8*1 = 167

示例 2：

输入：nums = [1,5]
输出：10

提示：

• n == nums.length
• 1 <= n <= 300
• 0 <= nums[i] <= 100

# Method 1: 记忆化搜索

参考 leetcode-solution

# Method 2: 动态规划

算法思路：

题目告知 “i - 1 或者 i + 1 超出数组边界时相当于一个数字为 1 的气球”，因此，可以为数组的首尾分别添加元素 1，以便处理边界问题（定义辅助数组 vector<int> val(nums.size() + 2) ）

定义 dp 数组：dp [i][j] 表示戳破区间 (i, j) 内所有气球所能获得的最高分数

初始化 dp 数组：当 i >= j 时，开区间 (i, j) 内没有气球，dp [i][j] = 0

递推公式：

• 假设 区间 (i, j) 内最后一个被戳破的气球 为 k
  • 在戳破气球 k 前，区间 (i, k) 内的所有气球均已被戳破，其获得的分数为 dp [i][k] ，区间 (k, j) 内的所有气球也均已被戳破，其获得的分数为 dp [k][j]
  • 气球 k 左侧为气球 i ，气球 k 右侧为气球 j ，即：戳破 k 获得的分数为 val [i] * val [k] * val [j]
  • 此时，区间 (i, j) 能获得的总分数为 dp [i][k] + val [i] * val [k] * val [j] + dp [k][j]
• 由于区间 (i, j) 具有多个可选的最后一个气球 k ，需要枚举 k 并选择总分数最高的，因此，递推公式为： dp[i][j] = max(dp[i][j], dp[i][k] + val[i] * val[k] * val[j] + dp[k][j]) ，其中， i + 1 <= k <= j - 1

遍历顺序：由递推公式可知，dp [i][j] 依赖于 dp [i][k] 和 dp [k][j] ，其中，i < k 且 k < j，因此，i 应按照从大到小的顺序遍历（为了获得 dp [k][j] ），j 应按照从小到大的顺序遍历（为了获得 dp [i][k] ）

或者，也可以按照对角线从左到右的顺序斜着遍历 dp 数组

代码实现：

int maxCoins(vector<int>& nums) {
    int n = nums.size();
    vector<int> val(n + 2, 0); // 创建一个辅助数组（在首尾各添 1），处理边界情况
    val[0] = val[n + 1] = 1;
    for (int i = 1; i <= n; ++i)
        val[i] = nums[i - 1];
    vector<vector<int>> dp(n + 2, vector<int>(n + 2, 0));
    for (int i = n; i >= 0; --i) { // 区间的左端点（开区间）
        for (int j = i + 1; j < n + 2; ++j) { // 区间的右端点（开区间）
            for (int k = i + 1; k < j; ++k) { // 区间内最后戳破的气球
                int tmp = dp[i][k] + val[i] * val[k] * val[j] + dp[k][j];
                dp[i][j] = max(dp[i][j], tmp); // 择优做选择
            }
        }
    }
    return dp[0][n + 1];
}

时间复杂度：$O(n^3)$，其中 $n$ 是数组 nums 的长度

• 状态数为 $n^2$
• 状态转移的复杂度为 $O(n)$

空间复杂度：$O(n^2)$

参考：

• angela：图解：动态规划解决戳气球问题，思路清晰简明，注释详细
• xiao-yan-gou：关键思路解释

# LeetCode 32. 最长有效括号

32. Longest Valid Parentheses

给你一个只包含 '(' 和 ')' 的字符串，找出最长有效（格式正确且连续）括号子串的长度。

示例 1：

输入：s = "(()"
输出：2
解释：最长有效括号子串是 "()"

示例 2：

输入：s = ")()())"
输出：4
解释：最长有效括号子串是 "()()"

示例 3：

输入：s = ""
输出：0

提示：

• $0 \le$ s.length $\le 3 \times 10^4$
• s[i] 为 '(' 或 ')'

# Method: 动态规划

算法思路：

定义 dp [i] 表示以 s [i] 结尾的最长有效括号的长度

初始化 dp [i] ：全都初始化为 0

推导 dp [i] 的状态转移过程：

• 若 s [i] == '(' ，无法形成以 s [i] 结尾的有效括号，则 dp [i] = 0
• 若 s [i] == ')' ，需要进一步分析前面的字符
  • 若 s [i - 1] == '(' ，则 s [i - 1] 可以与 s [i] 组成一对有效括号，因此：
    • 若 i - 2 <0 ，即 s [0, i] = "()" ，有 dp [i] = 2
    • 若 i - 2 >= 0 ，以 s [i] 结尾的最长有效括号的长度为 dp [i - 2] + 2
  • 若 s [i - 1] == ')' ，以 s [i] 结尾的最长有效括号只能是形如 “((...))” 的括号对，此时需要找到与 s [i] 配对的位置，即，i - dp [i - 1] - 1
    • 若 i - dp [i - 1] - 1 >= 0 且 s [i - dp [i - 1] - 1] == '(' ，则 s [i - dp [i - 1] - 1] 可以与 s [i] 组成有效括号，即，以 s [i] 结尾的最长有效括号的长度至少为 dp [i - 1] + 2
      • 需注意的是：可能存在以 s [i - dp [i - 1] - 2] 结尾的有效括号，即，可以将 “以 s [i - dp [i - 1] - 2] 结尾的有效括号” 与 “以 s [i - dp [i - 1] - 1] 起始的、以 s [i] 结尾的有效括号” 拼接
      • 因此，如果 i - dp [i - 1] - 2 >= 0 ，则以 s [i] 结尾的最长有效括号的长度为 dp [i - dp [i - 1] - 2] + dp [i - 1] + 2

确定遍历顺序：根据递推公式知，dp [i] 依赖于 dp [i - 1] 、dp [i - 2] 、dp [i - dp [i - 1] - 2] ，因此，应按照 i 从小到大的顺序遍历

遍历结束后，找出值最大的 dp [i] ，即为最长有效括号的长度

代码实现：

int longestValidParentheses(string s) {
    vector<int> dp(s.size(), 0);
    int ans = 0;
    for (int i = 1; i < s.size(); i++) {
        if (s[i] == ')') {
            if (s[i - 1] == '(') {
                if (i >= 2) dp[i] = dp[i - 2] + 2;
                else dp[i] = 2;
            } else if (i - dp[i - 1] - 1 >= 0 && s[i - dp[i - 1] - 1] == '(') {
                dp[i] = dp[i - 1] + 2;
                if (i - dp[i - 1] - 2 >= 0) {
                    dp[i] = dp[i] + dp[i - dp[i - 1] - 2];
                }
            }
            ans = max(ans, dp[i]);
        }
    }
    return ans;
}

时间复杂度：$O(n)$，其中 $n$ 是 s 的长度

空间复杂度：$O(n)$

参考：力扣官方题解

# LeetCode 322. 零钱兑换

322. Coin Change

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

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

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

示例 1：

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

示例 2：

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

示例 3：

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

提示：

• $1 \le$ coins.length $\le 12$
• $1 \le$ coins[i] $\le 2^{31} - 1$
• $0 \le$ amount $\le 10^4$

# 思路

每种面额的硬币可以重复选取，因此，本题属于完全背包问题，可以采用动态规划方法求解

其中，选取硬币的顺序并不影响结果，因此，外层遍历物品、内层遍历背包容量，或者，外层遍历背包容量、内层遍历物品，这两种遍历方案都可以

# Method: 动态规划

算法思路：

定义 dp 数组： dp[j] 表示凑成金额 j 所需的最少硬币个数，其中 0 <= j <= amount

递推公式：当 coins[i] <= j <= amount 时，若 dp[j - coins[i]] != INT_MAX ， dp[j] = min(dp[j], 1 + dp[j - coins[i]])

• 当 j < coins[i] 时，不能选取 coins[i] ， dp[j] 保持不变
• 当 coins[i] <= j <= amount 时，若选取 coins[i] ，所需的最少硬币数为 1 + dp[j - coins[i]] （注意，此时要求金额 j - coins[i] 是可以被凑出来的，即， dp[j - coins[i]] 不等于初始值），若不选取 coins[i] ，所需的最少硬币数为 dp[j] ，综合可得， dp[j] = min(dp[j], 1 + dp[j - coins[i]])

初始化 dp 数组：凑成金额 0 的硬币个数一定为 0 ，即， dp[0] = 0 。考虑到递推公式的特性， dp[j] 必须初始化为一个比较大的数值，以便在执行 dp[j] = min(dp[j], 1 + dp[j - coins[i]]) 时能够更新 dp 数组，因此，对任意 j > 0 均有 dp[j] = INT_MAX

遍历顺序：硬币的选取顺序不影响所需的最少硬币个数，可以采用外层遍历硬币面额（物品）、内层遍历金额之和（背包容量）

遍历结束后，若 dp[amount] 等于初始值 INT_MAX ，则说明任何一种硬币组合都无法组成金额 amount ，故而返回 -1 ，否则， dp[amount] 表示的就是所需的最少硬币个数

代码实现：

int coinChange(vector<int>& coins, int amount) {
    vector<int> dp(amount + 1, INT_MAX);
    dp[0] = 0;
    for (int i = 0; i < coins.size(); i++) {
        for (int j = coins[i]; j <= amount; j++) {
            if (dp[j - coins[i]] != INT_MAX) // 方案可行
                dp[j] = min(dp[j], 1 + dp[j - coins[i]]);
        }
    }
    if (dp[amount] == INT_MAX) return -1;    // 不存在可行的方案
    return dp[amount];
}

时间复杂度：$O(n \times amount)$ ，其中 $n$ 是数组的长度

空间复杂度：$O(amount)$

参考：代码随想录

# LeetCode 337. 打家劫舍 III

337. House Robber III

小偷又发现了一个新的可行窃的地区。这个地区只有一个入口，我们称之为 root 。

除了 root 之外，每栋房子有且只有一个 “父 “房子与之相连。一番侦察之后，聪明的小偷意识到 “这个地方的所有房屋的排列类似于一棵二叉树”。 如果 两个直接相连的房子在同一天晚上被打劫 ，房屋将自动报警。

给定二叉树的 root 。返回 在不触动警报的情况下 ，小偷能够盗取的最高金额 。

示例 1：

输入：root = [3,2,3,null,3,null,1]
输出：7
解释：小偷一晚能够盗取的最高金额 3 + 3 + 1 = 7

示例 2：

输入：root = [3,4,5,1,3,null,1]
输出：9
解释：小偷一晚能够盗取的最高金额 4 + 5 = 9

提示：

• 树的节点数在 $[1, 10^4]$ 范围内
• $0 \le$ Node.val $\le 10^4$

# Method: 递归 + 动态规划

确定递归函数的参数和返回值：

• 传入参数： TreeNode* root
• 返回值： vector<int>{val1, val2}
  • val1 表示不偷窃 root 节点时，从 root 的子树上偷窃所得的最大金额
  • val2 表示偷窃 root 节点时，从 root 及其子树上偷窃所得的最大金额

确定递归的终止条件：遇到空节点，无论是否偷窃，所得金额均为 0 ，故而返回 vector<int>(2, 0)

确定遍历顺序：采用后序遍历，因为需要根据子节点的返回值来处理当前节点

单层递归的逻辑：

• 递归左子树，计算偷窃左子节点、不偷窃左子节点所能达到的金额，分别记为 left[0] , left[1]
• 递归右子树，计算偷窃右子节点、不偷窃右子节点所能达到的金额，分别记为 right[0] , right[1]
• 处理当前节点
  • 如果不偷窃当前节点，则可以考虑偷窃子节点（并不一定要偷窃子节点），从左子树上所能得到的最大金额为 max(left[0], left[1]) ，从右子树上所能得到的最大金额为 max(right[0], right[1]) ，因此，总金额为 val1 = max(left[0], left[1]) + max(right[0], right[1])
  • 如果偷窃当前节点，则不能偷窃子节点，从左子树上得到的最大金额为 left[0] ，从右子树上得到的最大金额为 right[0] ，因此，总金额为 val2 = root->val + left[0] + right[0]

代码实现：

vector<int> dfs(TreeNode* root) {
    if (root == nullptr) return vector<int>{0, 0};
    vector<int> left = dfs(root->left);
    vector<int> right = dfs(root->right);
    int val1 = max(left[0], left[1]) + max(right[0], right[1]); // 偷窃 root 节点
    int val2 = root->val + left[0] + right[0];                  // 不偷窃 root 节点
    return vector<int>{val1, val2};
}

int rob(TreeNode* root) {
    vector<int> result = dfs(root);
    int ans = max(result[0], result[1]); // 处理根节点
    return ans;
}

时间复杂度：$O(n)$，其中 $n$ 为节点个数

空间复杂度：$O(n)$，递归使用栈空间

# LeetCode 343. 整数拆分

343. Integer Break

给定一个正整数 n ，将其拆分为 k 个 正整数 的和（ k >= 2 ），并使这些整数的乘积最大化。

返回 可以获得的最大乘积 。

示例 1：

输入：n = 2
输出：1
解释：2 = 1 + 1, 1 × 1 = 1.

示例 2：

输入：n = 10
输出：36
解释：10 = 3 + 3 + 4, 3 × 3 × 4 = 36.

提示：

• $2 \le$ n $\le 58$

# Method: 动态规划

算法思路：

1. 确定 dp 数组及其含义： dp[i] 表示将正整数 i 拆分后所能得到的最大乘积

2. 确定递推公式：

   • 假设拆分 i （ i >= 2 ）所得的第一个数为 j （ 1 <= j < i ），还剩 i - j ，做以下考虑
     • 不再拆分 i - j ，此时的乘积为 j * (i - j)
     • 继续将 i - j 拆成多个整数的和，此时的最大乘积为 j * dp[i - j]
     • 因此，对给定的 j ，最大乘积为 max(j * (i - j), j * dp[i - j])
   • 由于 j 可取 [1, i - 1] 区间内任意值，应遍历 j 才能得到 dp[i] ，即， dp[i] = max(dp[i], max(j * (i - j), j * dp[i - j]))

3. 初始化 dp 数组：可拆分的最小正整数为 2，而拆分 2 所得的最大乘积为 1 ，故而应初始化 dp[2] = 1

4. 确定遍历顺序：根据递推公式可知， dp[i] 依赖于 dp[i - j] ，故而应按 i 从小到大的顺序遍历；至于 j ，按从小到大顺序或从大到小顺序遍历均可

代码实现：

int integerBreak(int n) {
    vector<int> dp(n + 1, 0);
    dp[2] = 1;
    for (int i = 3; i <= n; i++) {
        for (int j = 1; j < i; j++) {
            dp[i] = max(dp[i], max(j * (i - j), j * dp[i - j]));
        }
    }
    return dp[n];
}

时间复杂度：$O(n^2)$

空间复杂度：$O(n)$

参考：代码随想录

# LeetCode 377. 组合总和 IV

377. Combination Sum IV

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

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

示例 1：

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

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

提示：

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

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

# 思路

nums 的每个元素可以选取多次，且需要考虑选取元素的顺序，因此本题计算的是选取元素的 排列 数

可以通过动态规划方法求解

其中，遍历顺序应为：外层 for 循环遍历背包容量，内层 for 循环遍历物品

# Method: 动态规划

算法思路

定义 dp 数组： dp[j] 表示选取元素之和等于 j 的硬币组合数，其中， 0 <= j <= target

递推公式： dp[j] += dp[j - nums[i]], nums[i] <= j <= target

• 若 j < nums[i] ，不能选取 nums[i] ，因此， dp[j] 保持不变
• 若 j >= nums[i] ，如果选取 nums[i] ，方案数应为 dp[j - nums[i]] ，如果不选取 nums[i] ，方案数应为 dp[j] ，综合两种情况，总的方案数为 dp[j] = dp[j] + dp[j - nums[i]]

初始化 dp 数组：不选取任何元素，元素之和才为 0 ，即， dp[0] = 1

遍历顺序：由于所求的是排列数，外层 for 循环应遍历元素之和（背包容量），内层 for 循环应遍历数组元素（物品），并且，均按照从小到大的顺序遍历

C++ 测试用例有两个数相加超过 int 的数据，因此需要加上 dp[j] + dp[j - nums[i]] < INT_MAX 这一限制

代码实现：

int combinationSum4(vector<int>& nums, int target) {
    vector<int> dp(target + 1, 0);
    dp[0] = 1;
    for (int j = 0; j <= target; j++) {
        for (int i = 0; i < nums.size(); i++) {
            if (j >= nums[i] && dp[j] + dp[j - nums[i]] < INT_MAX)
                dp[j] += dp[j - nums[i]];
        }
    }
    return dp[target];
}

时间复杂度：$O(n \times target)$，其中 $n$ 是数组的长度

空间复杂度：$O(target)$

# 进阶

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

如果给定的数组中含有负数，则会导致出现无限长度的排列

例如，假设数组中含有正整数 $a$ 和负整数 $−b$（其中 $a > 0$ , $b > 0$ ），则对于任意一个元素之和等于 $target$ 的排列，都可以在该排列的后面添加 $b$ 个 $a$ 和 $a$ 个 $−b$ ，使得新排列的元素之和依然等于 $target$ 。换而言之，只要存在一种符合条件的排列，就能构造出无限长度的排列

因此，必须限制排列的最大长度，避免出现无限长度的排列，才能计算排列数

参考：力扣官方题解

# LeetCode 392. 判断子序列

392. Is Subsequence

给定字符串 s 和 t ，判断 s 是否为 t 的子序列。

字符串的一个子序列是原始字符串删除一些（也可以不删除）字符而不改变剩余字符相对位置形成的新字符串。（例如，"ace" 是 "abcde" 的一个子序列，而 "aec" 不是）。

进阶：

如果有大量输入的 S，称作 S₁, S₂, ... , S_k ，其中 k $\ge$ 10⁹，你需要依次检查它们是否为 T 的子序列。在这种情况下，你会怎样改变代码？

示例 1：

输入：s = "abc", t = "ahbgdc"
输出：true

示例 2：

输入：s = "axc", t = "ahbgdc"
输出：false

提示：

• $0 \le$ s.length $\le 100$
• $0 \le$ t.length $\le 10^4$
• s 和 t 都只由小写字符组成

# Method 1: 双指针

算法思路：如果能够在字符串 t 中依次找到字符串 s 的每个字符，则说明 s 是 t 的子序列

算法流程：

定义指针 i 指向字符串 s ，指针 j 指向字符串 t

遍历 i 与 j ：

• 若 s[i] == t[j] ，说明在字符串 t 中找到了字符 s[i] ，可以继续寻找下一个字符，因此，同时移动 i 和 j ，
• 若 s[i] != t[j] ，则需继续在字符串 t 中寻找 s[i] ，因此，移动 j

遍历结束时，若 i 指向 s 的尾后，则说明 s 的所有字符都已在字符串 t 中找到，即，字符串 s 是字符串 t 的子序列

代码实现：

bool isSubsequence(string s, string t) {
    int i = 0;
    int j = 0;
    while (i < s.size() && j < t.size()) {
        if (s[i] == t[j]) i++;      // 字符串 t 中包含字符 s[i]
        j++;
    }
    if (i == s.size()) return true; // 字符串 t 中包含 s 的所有字符
    return false;
}

时间复杂度：$O(m + n)$，其中 $m$ 和 $n$ 分别是字符串 s 和字符串 t 的长度

空间复杂度：$O(1)$

# Method 2: 动态规划

算法思路：可以通过计算字符串 s 与字符串 t 的最长公共子序列长度来判断：若最长公共子序列长度等于字符串 s 的长度，则字符串 s 是字符串 t 的子序列；否则， s 不是 t 的子序列

可参考 LeetCode 1143. 最长公共子序列

算法流程：

定义 dp[i][j] 表示子串 s[0, i -1] 与子串 t[0, j - 1] 的最长公共子序列的长度

若 s[i - 1] == t[j - 1] ，则在 s[0, i - 2] 与 t[0, j - 2] 的基础上又找到了一个相同字符，因此， dp[i][j] = dp[i - 1][j - 1] + 1

若 s[i - 1] != t[j - 1] ，则 s[0, i - 1] 与 t[0, j - 2] 的最长公共子序列就是 s[0, i - 1] 与 t[0, j - 1] 的最长公共子序列，因此， dp[i][j] = dp[i][j - 1]

代码实现：

bool isSubsequence(string s, string t) {
    vector<vector<int>> dp(s.size() + 1, vector<int>(t.size() + 1, 0)); // dp[i][j] 表示 s[0, i - 1] 与 t[0, j - 1] 的最长公共子序列的长度
    for (int i = 1; i <= s.size(); i++) {
        for (int j = 1; j <= t.size(); j++) {
            if (s[i - 1] == t[j - 1]) dp[i][j] = dp[i - 1][j - 1] + 1;
            else dp[i][j] = dp[i][j - 1];
        }
    }
    return dp[s.size()][t.size()] == s.size();
}

时间复杂度：$O(m \times n)$，其中 $m$ 和 $n$ 分别是字符串 s 和字符串 t 的长度

空间复杂度：$O(m \times n)$

# 进阶

在前面的双指针法中，有大量的时间用于在 t 中找到下一个匹配字符

因此，可对字符串 t 进行预处理，计算出 “字符串 t 中任意位置到某字符下次出现时的距离” ，例如， i 位置 与 i 右侧第一次出现字符 j 位置的距离

为此，可将 dp 数组定义为： dp[i][j] 表示在字符串 t 中的位置 i 以右（包含 i ），字符 j + 'a' 第一次出现的位置

此时，对字符串 t 的预处理是与字符串 s 无关的，并且，在预处理完成后，可以利用 dp 数组信息计算出任意一个字符串 s 是否为 t 的子串，由此可解决 进阶 中的问题

具体可参考：力扣官方题解

# LeetCode 416. 分割等和子集

416. Partition Equal Subset Sum

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

示例 1：

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

示例 2：

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

提示：

• $1 \le$ nums.length $\le 200$
• $1 \le$ nums[i] $\le 100$

# Method: 动态规划

传统的 0-1 背包问题要求选取的物品的重量之和不超过背包的总容量，本题则要求选取的数字的和恰好等于数组元素和的一半（记作 target ）

# 思路一

首先判断数组是否可拆分：

• 若数组长度小于 2，不可能将将数组分成元素和相等的两个子集
• 若数组元素和为奇数，不可能将数组分成符合条件的两个子集
• 若 数组最大元素 超过 target ，也不可能将数组分成符合条件的两个子集

定义 dp 数组： dp[i][j] 表示 是否能从下标 [0, i] 的数组元素中选取若干正整数，使得被选取的元素之和等于 j ，其中， 0 <= 0 <= nums.size() - 1 ， 0 <= j <= target

确定递推公式：

• 若 j >= nums[i] ，做以下考虑
  • 选取 nums[i] ，则 dp[i][j] = dp[i - 1][j - nums[i]]
  • 不选取 nums[i] ，则 dp[i][j] = dp[i - 1][j]
  • 两种情况只要有一个为 true 就会有 dp[i][j] 为 true ，因此， dp[i][j] = dp[i - 1][j] || dp[i - 1][j - nums[i]]
• 若 j < nums[i] ，则 nums[i] 必不可能选取，因此有 dp[i][j] = dp[i - 1][j]

初始化 dp 数组：

• 当 i 为 0 时，只有 nums[0] 可被选取，故而 dp[0][nums[0]] = true 且 dp[0][0] = true （这一步要求 nums[0] 不大于 target ，而我们此前判断了数组最大元素是否超过 target ）
• 当 j 为 0 时，对任意 i 均有 dp[i][0] = true ，即，不选取任何数

代码实现：

bool canPartition(vector<int>& nums) {
    int n = nums.size();
    
    // 判断数组是否可拆分
    if (n < 2) return false;
    int sum = 0;
    int maxValue = 0;
    for (auto a : nums) {
        sum += a;
        maxValue = max(maxValue, a);
    }
    if (sum % 2 == 1) return false; // sum 为奇数，不可分割
    int target = sum / 2;
    if (maxValue > target) return false;

    // 定义 dp 数组及其初始化
    vector<vector<bool>> dp(n, vector<bool>(target + 1, false));
    for (int i = 0; i < n; i++)
        dp[i][0] = true;
    dp[0][nums[0]] = true;

    // 遍历
    for (int i = 1; i < n; i++) {
        for (int j = 1; j <= target; j++) {
            if (j < nums[i])
                dp[i][j] = dp[i - 1][j];
            else
                dp[i][j] = dp[i - 1][j] || dp[i - 1][j - nums[i]];
        }
    }

    return dp[n - 1][target];
}

时间复杂度：$O(n \times target)$，其中 $n$ 为数组长度，$target$ 是数组元素和的一半

空间复杂度：$O(n \times target)$

可采用一维 dp 数组实现，以优化算法空间复杂度

参考：力扣官方题解

# 思路二

本题可以将 target 当成背包的最大容量，并将 nums[i] 同时当成物品的重量和物品的价值。当背包内物品的总价值恰好等于 target 时，说明可以将 nums 数组分割成元素和相等的两个子集

首先判断数组是否可拆分：

• 若数组长度小于 2，不可能将将数组分成元素和相等的两个子集
• 若数组元素和为奇数，不可能将数组分成符合条件的两个子集

定义 dp 数组：在 [0, i] 范围内选择物品，放进容量为 j 的背包内，其最大价值为 dp[i][j] ，其中， 0 <= 0 <= nums.size() - 1 ， 0 <= j <= target

确定递推公式：当 j >= nums[i] 时， dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - nums[i]] + nums[i])

• 若 j >= nums[i] ，做以下考虑
  • 选取 nums[i] ，此时，背包最大价值为 dp[i - 1][j - nums[i]] + nums[i]
  • 不选取 nums[i] ，此时，背包最大价值为 dp[i - 1][j]
  • 综合两种情况，应选择价值最大的，即 dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - nums[i]] + nums[i])
• 若 j < nums[i] ，则 nums[i] 必不可能选取，因此有 dp[i][j] = dp[i - 1][j]

初始化 dp 数组：

• 当 i = 0 时，若 j < nums[0] ，背包放不下物品 0 ，则 dp[0][j] = 0 ，若 j >= nums[0] ，应选取物品 0 使得背包价值最大，即 dp[0][j] = nums[0]
• 当背包容量为 0 时， dp[i][0] = 0

其代码实现类似于思路一，这里不再给出具体代码

鉴于空间复杂度较高，下面给出一维 dp 数组的代码实现：

bool canPartition(vector<int>& nums) {
    int n = nums.size();
    if (n < 2) return false;
    int sum = 0;
    for (int i = 0; i < n; i++)
        sum += nums[i];
    if (sum % 2) return false;
    int target = sum / 2;

    // 0-1 背包
    vector<int> dp(target + 1, 0);
    for (int i = 0; i < n; i++)
        for (int j = target; j >= nums[i]; j--)
            dp[j] = max(dp[j], dp[j - nums[i]] + nums[i]);

    return dp[target] == target ? true : false; // 判断背包最大价值是否恰好为 target
}

时间复杂度：$O(n \times target)$，其中 $n$ 为数组长度，$target$ 是数组元素和的一半

空间复杂度：$O(target)$

参考：代码随想录

# LeetCode 474. 一和零

474. Ones and Zeroes

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

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

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

示例 1：

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

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

提示：

• $1 \le$ strs.length $\le 600$
• $1 \le$ strs[i].length $\le 100$
• strs[i] 仅由 '0' 和 '1' 组成
• $1 \le$ m , n $\le 100$

# 思路

本题和 0-1 背包问题非常相似，但是本题的背包有两种容量，即选取的字符串子集中的 0 和 1 的数量上限

因此，动态规划需要遍历三个维度：字符串、0 的容量、1 的容量

# Method: 动态规划

算法思路：

1. dp 数组

   • dp[i][j][k] ：在确保 0 的个数不超过 i 、1 的个数不超过 j 的情况下，从索引 [0, i] 范围内选出字符串，所能达到的最大子集的长度
   • 其中， 0 <= i <= strs.size() - 1 ， 0 <= j <= m ， 0 <= k <= n

2. 递推公式：当 1 <= i < strs.size() 时，计算 strs[i] 中 0 和 1 的个数，分别记作 num0 和 num1

   • 若 j < num0 或 k < num1 ：不能选取 strs[i] 这一字符串，此时， dp[i][j][k] = dp[i - 1][j][k]
   • 若 j >= num0 且 k >= num1 ：如果选取 strs[i] ，最大子集的长度为 1 + dp[i - 1][j - num0][k - num1] ，如果不选取 strs[i] ，最大子集的长度为 dp[i - 1][j][k] ，因此， dp[i][j][k] = max(1 + dp[i - 1][j - num0][k - num1], dp[i - 1][j][k])

3. 初始化 dp 数组：当 i = 0 时，对满足 j >= num0 && k >= num1 的任意 j 和 k ，都应选取 strs[0] 这一字符串，即， dp[0][j][k] = 1

4. 遍历顺序

   • 最外层遍历 i ，按从小到大顺序遍历
   • 中层遍历 j ，按从小到大顺序遍历
   • 内层遍历 k ，按从小到大顺序遍历

也可以中层遍历 k ，内层遍历 j

代码实现：

int numberOfZero(string s) { // 统计字符串 s 中的 0 的个数
    int count = 0;
    for (auto c : s)
        if (c == '0') count++;
    return count;
}

int findMaxForm(vector<string>& strs, int m, int n) {
    
    // 定义 dp 数组
    int size = strs.size();
    vector<vector<vector<int>>> dp(size, vector<vector<int>>(m + 1, vector<int>(n + 1, 0)));
    
    // 初始化
    int num0 = numberOfZero(strs[0]);
    int num1 = strs[0].size() - num0;
    for (int j = num0; j <= m; j++) {
        for (int k = num1; k <= n; k++) {
            dp[0][j][k] = 1;
        }
    }

    // 遍历
    for (int i = 1; i < size; i++) {
        num0 = numberOfZero(strs[i]);
        num1 = strs[i].size() - num0;
        for (int j = 0; j <= m; j++) {
            for (int k = 0; k <= n; k++) {
                if (num0 <= j && num1 <= k)
                    dp[i][j][k] = max(dp[i - 1][j][k], 1 + dp[i - 1][j - num0][k - num1]);
                else
                    dp[i][j][k] = dp[i - 1][j][k];
            }
        }
    }

    // 返回目标值
    return dp[size - 1][m][n];
    
}

时间复杂度：$O(l m n + L)$，其中 $l$ 是数组 strs 的长度，$L$ 是数组 strs 中所有字符串的长度之和

• 动态规划需要分别遍历 i 、 j 、 k ，时间复杂度为 $O(l m n)$
• 需要计算 strs 中每个字符串的 0 和 1 的数量，因此需要 $O(L)$ 的时间来遍历所有的字符串

空间复杂度：$O(l m n)$，三维 dp 数组所需空间

参考：力扣官方题解

# 优化

可定义二维 dp 数组，降低空间复杂度

其中， dp[j][k] ：最多 j 个 0 、 k 个 1 时，所能达到的最大子集的长度

此时， j 和 k 都要按从大到小的顺序遍历

代码实现：

int numberOfZero(string s) { // 统计字符串 s 中的 0 的个数
    int count = 0;
    for (auto c : s)
        if (c == '0') count++;
    return count;
}

int findMaxForm(vector<string>& strs, int m, int n) {
    // 定义 dp 数组
    vector<vector<int>> dp(m + 1, vector<int>(n + 1, 0));
    // 遍历
    for (int i = 0; i < strs.size(); i++) {
        int num0 = numberOfZero(strs[i]);
        int num1 = strs[i].size() - num0;
        for (int j = m; j >= num0; j--) {
            for (int k = n; k >= num1; k--) {
                dp[j][k] = max(dp[j][k], 1 + dp[j - num0][k - num1]);
            }
        }
    }
    // 返回目标值
    return dp[m][n];
}

时间复杂度：$O(l m n + L)$，其中 $l$ 是数组 strs 的长度，$L$ 是数组 strs 中所有字符串的长度之和

空间复杂度：$O(m n)$，二维 dp 数组所需空间

# LeetCode 494. 目标和

494. Target Sum

给你一个整数数组 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 \le$ nums.length $\le 20$
• $0 \le$ nums[i] $\le 1000$
• $0 \le$ sum(nums[i]) $\le 1000$
• $-1000 \le$ target $\le 1000$

# Method 1: 深度优先搜索

# 算法思路

遍历所有的表达式，即，为每个数字分别添加符号 + 或 - ，判断表达式的结果是否等于 target

# 代码实现

int ans = 0;

void DFS(vector<int>& nums, int start, int sum, int target) {
    if (start == nums.size()) {
        if (sum == target) ++ans;
        return;
    }
    DFS(nums, start + 1, sum + nums[start], target);
    DFS(nums, start + 1, sum - nums[start], target);
}

int findTargetSumWays(vector<int>& nums, int target) {
    DFS(nums, 0, 0, target);
    return ans;
}

# 复杂度分析

时间复杂度：$(2^n)$，其中 $n$ 是数组 nums 的长度，一共需要遍历 $2^n$ 种表达式

空间复杂度：$O(n)$，递归所需栈空间

# Method 2: 动态规划

# 算法思路

记数组的元素和为 $sum$ ，添加 - 的元素之和为 $neg$ ，添加 + 的元素之和则为 $sum − neg$

所得的表达式为

$$(sum - neg) - neg = sum - 2 \times neg = target$$

由此可得

$$neg = \frac{sum - target}{2}$$

由于 nums 数组中的元素均为非负整数，其组成的 $neg$ 也必定为非负整数，因此，$sum - target$ 应为 非负偶数。否则， nums 数组元素无法组成 $neg$ ，也无法得到值为 $target$ 的表达式，直接返回 0

若上式成立，问题转化为：从数组 nums 中选取若干元素，使得这些元素之和等于 $neg$ ，计算选取元素的方案数

即，0-1 背包问题，可采用动态规划方法求解，类似于 LeetCode 416. 分割等和子集 和 LeetCode 1049. 最后一块石头的重量 II

参考：力扣官方题解

# 算法流程

定义 dp 数组： dp[j] 表示元素和为 j 的方案数，其中， 0 <= j <= neg

确定递推公式： dp[j] = dp[j] + dp[j - nums[j]], nums[i] <= j <= neg

• 当 j < nums[i] 时，不能选择 nums[i] ， dp[j] 应保持不变
• 当 j >= nums[i] 时，若选取 nums[i] ，则元素和等于 j 的方案数为 dp[j - nums[j]] ，若不选取 nums[j] ，则方案数为 dp[j] ，综合两种情况可得 dp[j] = dp[j] + dp[j - nums[j]]

初始化 dp 数组： dp[0] = 1

• 当 j 为 0 时，任意 nums[i] 均不可被选择，对应的方案数为 1，即 dp[0] = 1

确定遍历顺序：

• 外层遍历 i ，内层遍历 j
• i 按从小到大顺序遍历， j 按从大到小顺序遍历

最终得到 dp[neg] 即为所求

# 代码实现

int findTargetSumWays(vector<int>& nums, int target) {
    int n = nums.size();
    int sum = 0;
    for (int a : nums)
        sum += a;
    
    int diff = sum - target;
    if (diff < 0 || diff % 2) return 0;
    int neg = diff / 2;

    vector<int> dp(neg + 1, 0);
    dp[0] = 1;
    for (int i = 0; i < n; i++) {
        for (int j = neg; j >= nums[i]; j--) {
            dp[j] += dp[j - nums[i]];
        }
    }

    return dp[neg];
}

# 复杂度分析

时间复杂度：$O(n \times neg)$，其中 $n$ 是数组 nums 的长度，$neg$ 为添加 - 的元素之和

空间复杂度：$O(neg)$，dp 数组所需空间

# LeetCode 5. 最长回文子串

5. Longest Palindromic Substring

给你一个字符串 s ，找到 s 中最长的回文子串。

如果字符串的反序与原始字符串相同，则该字符串称为回文字符串。

示例 1：

输入：s = "babad"
输出："bab"
解释："aba" 同样是符合题意的答案。

示例 2：

输入：s = "cbbd"
输出："bb"

提示：

• 1 $\le$ s.length $\le$ 1000
• s 仅由数字和英文字母组成

# Method: 动态规划

算法思路：

定义 dp 数组： dp[i][j] 表示 [i, j] 区间范围内的子串是否为回文子串，其中， 0 <= i <= s.size() - 1 ， i <= j <= s.size() - 1

初始化 dp 数组：全都初始化为 false

推导状态转移过程：当 s[i] == s[j] 时，考虑以下情况：

• j - i == 0 ：即，只有一个字符，此时一定为回文子串，即， dp[i][j] = true
• j - i == 1 ：即，只有 s[i] 和 s[j] 这两个相同的字符，此时也为回文子串，即， dp[i][j] = true
• j - i > 1 ：此时， s[i, j] 多于两个字符，若 s[i + 1, j - 1] 是回文子串，则 s[i, j] 也是回文子串，因此， dp[i][j] = dp[i + 1][j - 1]

确定遍历顺序：根据递推公式知， dp[i][j] 依赖于 dp[i + 1][j - 1] ，因此，应按照从大到小的顺序遍历 i ，按照从小到大的顺序遍历 j

由于本题要求的是最长回文子串，因此，在遍历 dp 数组时，还需要维护最长回文子串的起点和长度

代码实现：

string longestPalindrome(string s) {
    vector<vector<bool>> dp(s.size(), vector<bool>(s.size(), false));
    int len = 0;    // 最长回文子串的长度
    int start = 0;  // 最长回文子串的起点
    for (int i = s.size() - 1; i >= 0; i--) {
        for (int j = i; j < s.size(); j++) {
            if (s[i] == s[j] && (j - i <= 1 || dp[i + 1][j - 1])) {
                dp[i][j] = true;
                if (j - i + 1 > len) { // 更新最长回文子串
                    len = j - i + 1;
                    start = i;
                }
            }
        }
    }
    return s.substr(start, len); // 以 start 为起点的、长为 len 的回文子串
}

时间复杂度：$O(n^2)$，其中 $n$ 是字符串 s 的长度

空间复杂度：$O(n^2)$

# LeetCode 509. 斐波那契数

LeetCode 509. Fibonacci Number

斐波那契数（通常用 F(n) 表示）形成的序列称为 斐波那契数列 。该数列由 0 和 1 开始，后面的每一项数字都是前面两项数字的和。也就是：

F(0) = 0, F(1) = 1
F(n) = F(n - 1) + F(n - 2), for n > 1.

给定 n ，请计算 F(n) 。

示例 1：

输入：n = 2
输出：1
解释：F(2) = F(1) + F(0) = 1 + 0 = 1

示例 2：

输入：n = 3
输出：2
解释：F(3) = F(2) + F(1) = 1 + 1 = 2

示例 3：

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

提示：

• $0 \le$ n $\le 30$

# Method: 动态规划

算法思路：

1. 确定 dp 数组及其含义： dp[i] 表示第 i 个斐波那契数，即， F(i)

2. 确定递推公式：当 i >= 2 时， dp[i] = dp[i - 1] + dp[i - 2]

3. 初始化 dp 数组： dp[0] = 0 ， dp[1] = 1

4. 确定遍历顺序：根据递推公式可知， dp[i] 依赖于 dp[i - 1] 和 dp[i - 2] ，因此，应按 i 从小到大遍历

5. 举例推导 dp 数组

最后的 dp[n] 就是所求的斐波那契数

代码实现：

int fib(int n) {
    if (n == 0) return 0;
    if (n == 1) return 1;
    vector<int> dp(n + 1, 0);
    dp[1] = 1;
    for (int i = 2; i <= n; i++) {
        dp[i] = dp[i - 2] + dp[i - 1];
    }
    return dp[n];
}

时间复杂度：$O(n)$

空间复杂度：$O(n)$

# 优化

由于 dp[i] 仅依赖于 dp[i - 1] 和 dp[i - 2] ，也可以只维护 dp[0] 和 dp[1] ，而不需要记录整个 dp 数组

• 当 i 是奇数时，斐波那契数 F(i) 存放在 dp[1] 中
• 当 i 是偶数时，斐波那契数 F(i) 存放在 dp[0] 中

最后的 dp[n & 1] 就是所求的斐波那契数

代码实现：

int fib(int n) {
    if (n <= 1) return n;
    vector<int> dp = {0, 1};
    for (int i = 2; i <= n; i++) {
        dp[i & 1] = dp[(i - 2) & 1] + dp[(i - 1) & 1];
    }
    return dp[n & 1];
}

时间复杂度：$O(n)$

空间复杂度：$O(1)$

# LeetCode 516. 最长回文子序列

516. Longest Palindromic Subsequence

给你一个字符串 s ，找出其中最长的回文子序列，并返回该序列的长度。

子序列定义为：不改变剩余字符顺序的情况下，删除某些字符或者不删除任何字符形成的一个序列。

示例 1：

输入：s = "bbbab"
输出：4
解释：One possible longest palindromic subsequence is "bbbb".

示例 2：

输入：s = "cbbd"
输出：2
解释：One possible longest palindromic subsequence is "bb".

提示：

• $1 \le$ s.length $\le 1000$
• s 仅由小写英文字母组成

# Method: 动态规划

算法思路：

定义 dp 数组： dp[i][j] 表示 [i, j] 区间范围内的最长回文子序列的长度，其中， 0 <= i <= s.size() - 1 ， i <= j <= s.size() - 1

初始化 dp 数组：任何一个长为 1 的子序列都是回文子序列，因此， dp[i][i] == 1

推导 dp[i][j] 的状态转移过程：

• 当 s[i] == s[j] 时，针对 [i + 1, j - 1] 区间内的最长回文子序列，可在其首端和尾端分别添加 s[i] 和 s[j] ，以形成更长的回文子序列，因此，最大长度为 dp[i][j] = dp[i + 1][j - 1] + 2
• 当 s[i] != s[j] 时，则 s[i] 和 s[j] 不能同时作为某一个回文子序列的首尾，因此：
  • 考虑 [i, j - 1] 区间内的最长回文子序列，最大长度为 dp[i][j - 1]
  • 考虑 [i + 1, j] 区间内的最长回文子序列，最大长度为 dp[i + 1][j]
  • 综合两种情况，取最大值，即， dp[i][j] = max(dp[i][j - 1], dp[i + 1][j])

确定遍历顺序：根据递推公式知， dp[i][j] 依赖于 dp[i + 1][j - 1] ，因此，应按照从大到小的顺序遍历 i ，按照从小到大的顺序遍历 j

遍历结束后， dp[0][s.size() - 1] 即为字符串 s 的最长回文子序列的长度

代码实现：

int longestPalindromeSubseq(string s) {
    vector<vector<int>> dp(s.size(), vector<int>(s.size(), 0));
    for (int i = 0; i < s.size(); i++) dp[i][i] = 1;
    for (int i = s.size() - 1; i >= 0; i--) {
        for (int j = i + 1; j < s.size(); j++) {
            if (s[i] == s[j])
                dp[i][j] = dp[i + 1][j - 1] + 2;
            else
                dp[i][j] = max(dp[i + 1][j], dp[i][j - 1]);
        }
    }
    return dp[0][s.size() - 1];
}

时间复杂度：$O(n^2)$，其中 $n$ 是字符串 s 的长度

空间复杂度：$O(n^2)$

# LeetCode 518. 零钱兑换 II

518. Coin Change 2

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

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

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

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

示例 1：

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

示例 2：

输入：amount = 3, coins = [2]
输出：0
解释：只用面额 2 的硬币不能凑成总金额 3

示例 3：

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

提示：

• $1 \le$ coins.length $\le 300$
• $1 \le$ coins[i] $\le 5000$
• coins 中的所有值 互不相同
• $0 \le$ amount $\le 5000$

# 思路

coins 的每个元素可以选取多次，且不考虑选取元素的顺序，因此本题计算的是选取硬币的 组合 数

本题是一个完全背包问题，可以通过动态规划方法求解

完全背包问题的遍历顺序：

• 如果求的是组合数，外层 for 遍历物品，内层 for 遍历背包
• 如果求的是排列数，外层 for 遍历背包，内层 for 遍历物品

# Method: 动态规划

算法思路：

定义 dp 数组： dp[j] 表示凑成金额 j 的硬币组合数，其中， 0 <= j <= amount

递推公式： dp[j] += dp[j - coins[i]], coins[i] <= j <= amount

• 若 j < coins[i] ，不能选取 coins[i] ，因此， dp[j] 保持不变
• 若 j >= coins[i] ，如果选取 coins[i] ，凑成金额 j 的方案数应为 dp[j - coins[i]] ，如果不选取 coins[i] ，凑成 j 的方案数应为 dp[j] ，综合两种情况，总的方案数为 dp[j] = dp[j] + dp[j - coins[i]]

初始化 dp 数组：只有不选取任何硬币时，金额之和才为 0 ，即，金额 0 只对应 1 种硬币组合，因此， dp[0] = 1

遍历顺序：外层遍历硬币面额，内层遍历金额总和，并且，均按照从小到大的顺序遍历

• 不同于 动态规划 中的纯完全背包问题（要求的是能否凑成某个金额、凑成的最大金额是多少），纯完全背包可以改变两个 for 循环的嵌套方式，本题（要求的是凑成某金额的方案个数）只能外层遍历物品（硬币面额），内层遍历背包容量（金额总和）
• 外层遍历硬币面额，内层遍历金额总和：只可能出现 $\{coins[i],\ coins[i + 1]\}$ 这种情况，而不会出现 $\{coins[i + 1],\ coins[i]\}$ 的情况，即，硬币面额的出现顺序是确定的，因此，只会计算组合数，而不会计算排列数
• 外层遍历金额总和，内层遍历硬币面额：可能会既出现 $\{coins[i],\ coins[i + 1]\}$ ，又出现 $\{coins[i + 1],\ coins[i]\}$ ，即，硬币面额的出现顺序并不确定，因此，这里会计算排列数

例如 coins = [1,2] ，对于 dp[3] 的计算，一定是先遍历硬币面额 1 然后才遍历硬币面额 2，故而只会统计 3 = 1 + 1 + 1 和 3 = 1 + 2 这两种情况。硬币面额 2 不可能出现在硬币面额 1 之前，即，不会重复计算 3 = 2 + 1 的情况

建议把这两种方案的 dp 数组打印出来，对比一下

最后的 dp[amount] 即为所求

代码实现：

int change(int amount, vector<int>& coins) {
    vector<int> dp(amount + 1, 0);
    dp[0] = 1;
    for (int i = 0; i < coins.size(); i++) {
        for (int j = coins[i]; j <= amount; j++) {
            dp[j] += dp[j - coins[i]];
        }
    }
    return dp[amount];
}

时间复杂度：$O(n \times amount)$，其中 $n$ 是数组的长度，$amount$ 是总金额

空间复杂度：$O(amount)$

参考：

• 代码随想录
• 力扣官方题解

# LeetCode 583. 两个字符串的删除操作

583. Delete Operation for Two Strings

给定两个单词 word1 和 word2 ，返回使得 word1 和 word2 相同所需的最小步数。

每步 可以删除任意一个字符串中的一个字符。

示例 1：

输入：word1 = "sea", word2 = "eat"
输出：2
解释：第一步将 "sea" 变为 "ea" ，第二步将 "eat "变为 "ea"

示例 2：

输入：word1 = "leetcode", word2 = "etco"
输出：4

提示：

• $1 \le$ word1.length , word2.length $\le 500$
• word1 和 word2 只包含小写英文字母

# Method 1: 最长公共子序列

要通过删除字符使得 word1 与 word2 相同，也就是要得到 word1 与 word2 的公共子序列

因此，本题可以通过 word1 与 word2 的最长公共子序列的长度来计算：

• 令 $m$ 表示 word1 的长度，$n$ 表示 word2 的长度，$k$ 表示 word1 与 word2 的最长公共子序列的长度
• 要使 word1 与 word2 相同，则应删除最长公共子序列以外的所有字符。即，word1 需要删除 $m - k$ 个字符，word2 需要删除 $n - k$ 个字符
• 因此，所需的最少步数为 $m + n - 2 k$

其中，最长公共子序列长度的计算可参考 LeetCode 1143. 最长公共子序列

代码实现：

int minDistance(string word1, string word2) {
    int m = word1.size();
    int n = word2.size();
    vector<vector<int>> dp(m + 1, vector<int>(n + 1, 0));
    for (int i = 1; i <= m; i++) {
        for (int j = 1; j <= n; j++) {
            if (word1[i - 1] == word2[j - 1])
                dp[i][j] = dp[i - 1][j - 1] + 1;
            else
                dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
        }
    }
    int ans = m + n - (2 * dp[m][n]);
    return ans;
}

时间复杂度：$O(m \times n)$ ，其中 $m$ 和 $n$ 分别是 word1 和 word2 的长度

空间复杂度：$O(m \times n)$

# Method 2: 动态规划

算法思路：

定义 dp 数组： dp[i][j] 表示使得 word1[0, i - 1] 与 word2[0, j - 1] 相同所需的最少删除次数，其中， 1 <= i <= word1.size() , 1 <= j <= word2.size()

初始化 dp[i][0] 与 dp[0][j] ：

• [dp][i][0] ：此时， word2[0, j - 1] 为空字符串，要使得 word1[0, i - 1] 与空字符串相等，应将 word1[0, i - 1] 中的全部字符都删除，即， dp[i][0] = i
• [dp][0][j] ：此时， word1[0, i - 1] 为空字符串，要使得 word2[0, j - 1] 与空字符串相等，应将 word2[0, j - 1] 中的全部字符都删除，即， dp[i][0] = j

推导 dp[i][j] 的状态转移过程：

• 当 word1[i - 1] == word2[j - 1] 时，无需删除 word1[i - 1] 与 word2[j - 1] ，计算使 word1[0, i - 2] 与 word2[0, j - 2] 相同所需的最少删除次数即可，即， dp[i][j] = dp[i - 1][j - 1]
• 当 word1[i - 1] != word2[j - 1] 时，做以下考虑
  • 若删除 word1[i - 1] ，则应使 word1[0, i - 2] 与 word2[j - 1] 相同，此时，所需的最少删除次数为 1 + dp[i - 1][j]
  • 若删除 word2[j - 1] ，则应使 word1[0, i - 1] 与 word2[0, j - 2] 相同，此时，所需的最少删除次数为 1 + dp[i][j - 1]
  • 综合两种情况，取最小值，即， dp[i][j] = min(1 + dp[i - 1][j], 1 + dp[i][j - 1])

确定遍历顺序：根据状态转移方程知， dp[i][j] 依赖于 dp[i - 1][j - 1] ， dp[i - 1][j] 和 dp[i][j - 1] ，因此，应按照从小到大的顺序遍历 i 和 j

遍历结束后， dp[word1.size()][word2.size()] 即为所求

代码实现：

int minDistance(string word1, string word2) {
    int m = word1.size();
    int n = word2.size();
    vector<vector<int>> dp(m + 1, vector<int>(n + 1, 0));
    for (int i = 0; i <= m; i++) dp[i][0] = i;
    for (int j = 0; j <= n; j++) dp[0][j] = j;
    for (int i = 1; i <= m; i++) {
        for (int j = 1; j <= n; j++) {
            if (word1[i - 1] == word2[j - 1])
                dp[i][j] = dp[i - 1][j - 1];
            else
                dp[i][j] = min(dp[i - 1][j], dp[i][j - 1]) + 1;
        }
    }
    return dp[m][n];

}

时间复杂度：$O(m \times n)$ ，其中 $m$ 和 $n$ 分别是 word1 和 word2 的长度

空间复杂度：$O(m \times n)$

参考：力扣官方题解

# LeetCode 62. 不同路径

62. Unique Paths

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

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

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

示例 1：

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

示例 2：

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

示例 3：

输入：m = 3, n = 3
输出：6

提示：

• $1 \le$ m , n $\le 100$
• 题目数据保证答案小于等于 $2 \times 10^9$

# Method: 动态规划

算法思路：

1. 确定 dp 数组及其含义： dp[i][j] 表示从 (0, 0) 到达 (i, j) 位置的路径条数，其中， 0 <= i <= m - 1 ， 0 <= j <= n - 1

2. 确定递推公式

   • (0, j) 只能由 (0, j - 1) 向右移动一步到达，故而 dp[0][j] = 1
   • (i, 0) 只能由 (i - 1, 0) 向下移动一步到达，故而 dp[i][0] = 1
   • 对任意 i > 0 且 j > 0 ， (i, j) 可由 (i - 1, j) 向下移动到达，也可由 (i, j - 1) 向右移动到达，故而 dp[i][j] = dp[i - 1][j] + dp[i][j - 1]

3. 初始化 dp 数组： dp[0][j] = 1 ， dp[i][0] = 1

4. 确定遍历顺序：根据递推公式可知， dp[i][j] 依赖于 dp[i - 1][j] 和 dp[i][j - 1] ，因此，应按 i 从小到大、 j 从小到大顺序遍历

5. 举例推导 dp 数组

代码实现：

int uniquePaths(int m, int n) {
    vector<vector<int>> dp(m, vector<int>(n, 0)); // 从 (0, 0) 到 (i, j) 的路径条数
    for (int i = 0; i < m; i++) dp[i][0] = 1;
    for (int j = 1; 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];
}

时间复杂度：$O(m \times n)$

空间复杂度：$O(m \times n)$

# LeetCode 63. 不同路径 II

63. Unique Paths 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

提示：

• m == obstacleGrid.length
• n == obstacleGrid[i].length
• $1 \le$ m , n $\le 100$
• obstacleGrid[i][j] 为 0 或 1

# Method: 动态规划

算法思路：

1. 确定 dp 数组及其含义： dp[i][j] 表示从 (0, 0) 到达 (i, j) 位置的路径条数，其中， 0 <= i <= m - 1 ， 0 <= j <= n - 1

2. 确定递推公式

   • 对任意 (i, j) ，若 (i, j) 有障碍物，则无法到达 (i, j) ，即， dp[i][j] = 0
   • 否则， (i, j) 可由 (i - 1, j) 向下移动到达，也可由 (i, j - 1) 向右移动到达，即， dp[i][j] = dp[i - 1][j] + dp[i][j - 1]

3. 初始化 dp 数组：

   • 到达 (i, 0) 的路径只有一条，即 dp[i][0] = 1 ，但如果某个 (i0, 0) 存在障碍物，则对任意 i >= i0 均有 dp[i][0] = 0
   • 到达 (0, j) 的路径只有一条，即 dp[0][j] = 1 ，但如果某个 (0, j0) 存在障碍物，则对任意 j >= j0 均有 dp[0][j] = 0

   vector<vector<int>> dp(m, vector<int>(n, 0));
   for (int i = 0; i < m && obstacleGrid[i][0] == 0; i++) // 遇到障碍物则停止赋 1
       dp[i][0] = 1;
   for (int j = 0; j < n && obstacleGrid[0][j] == 0; j++) // 遇到障碍物则停止赋 1
       dp[0][j] = 1;
   

4. 确定遍历顺序：根据递推公式可知， dp[i][j] 依赖于 dp[i - 1][j] 和 dp[i][j - 1] ，因此，应按 i 从小到大、 j 从小到大顺序遍历

5. 举例推导 dp 数组

代码实现：

int uniquePathsWithObstacles(vector<vector<int>>& obstacleGrid) {
    int m = obstacleGrid.size();
    int n = obstacleGrid[0].size();
    vector<vector<int>> dp(m, vector<int>(n, 0));
    for (int i = 0; i < m && obstacleGrid[i][0] == 0; i++) // 注意这里要从 i = 0 开始，因为 (0, 0) 可能有障碍物
        dp[i][0] = 1;
    for (int j = 0; j < n && obstacleGrid[0][j] == 0; j++) // 注意这里要从 j = 0 开始，因为 (0, 0) 可能有障碍物
        dp[0][j] = 1;
    for (int i = 1; i < m; i++) {
        for (int j = 1; j < n; j++) {
            if (obstacleGrid[i][j] == 1) continue; // (i,j) 处有障碍物，无法到达
            dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
        }
    }
    return dp[m - 1][n - 1];
}

时间复杂度：$O(m \times n)$

空间复杂度：$O(m \times n)$

参考：代码随想录

# LeetCode 64. 最小路径和

64. Minimum Path Sum

给定一个包含非负整数的 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

提示：

• m == grid.length
• n == grid[i].length
• $1 \le$ m , n $\le 200$
• $0 \le$ grid[i][j] $\le 100$

# Method: 动态规划

代码实现：

int minPathSum(vector<vector<int>>& grid) {
    
    // 定义 dp 数组
    int m = grid.size();
    int n = grid[0].size();
    vector<vector<int>> dp(m, vector<int>(n, 0)); // dp[i][j] 表示从左上角到达 (i, j) 位置的最小路径和
    
    // 初始化
    dp[0][0] = grid[0][0];
    for (int i = 1; i < m; i++)
        dp[i][0] = dp[i - 1][0] + grid[i][0];
    for (int j = 1; j < n; j++)
        dp[0][j] = dp[0][j - 1] + grid[0][j];
    
    // 更新 dp 数组
    for (int i = 1; i < m; i++) {
        for (int j = 1; j < n; j++) {
            dp[i][j] = min(dp[i - 1][j], dp[i][j - 1]) + grid[i][j];
        }
    }
    
    // 目标值
    return dp[m - 1][n - 1];
}

时间复杂度：$O(m n)$，其中 $m$ 和 $n$ 分别是网格的行数和列数

空间复杂度：$O(m n)$

可以使用滚动数组来降低空间复杂度

# LeetCode 647. 回文子串

647. Palindromic Substrings

给你一个字符串 s ，请你统计并返回这个字符串中 回文子串 的数目。

回文字符串 是正着读和倒过来读一样的字符串。

子字符串 是字符串中的由连续字符组成的一个序列。

具有不同开始位置或结束位置的子串，即使是由相同的字符组成，也会被视作不同的子串。

示例 1：

输入：s = "abc"
输出：3
解释：3 个回文子串: "a", "b", "c"

示例 2：

输入：s = "aaa"
输出：6
解释：6 个回文子串: "a", "a", "a", "aa", "aa", "aaa"

提示：

• $1 \le$ s.length $\le 1000$
• s 由小写英文字母组成

# Method: 动态规划

算法思路：

定义 dp 数组： dp[i][j] 表示 [i, j] 区间范围内的子串是否为回文子串，其中， 0 <= i <= s.size() - 1 ， i <= j <= s.size() - 1

初始化 dp 数组：全都初始化为 false

推导状态转移过程：

• 当 s[i] != s[j] 时， s[i, j] 不可能是回文子串， dp[i][j] = false
• 当 s[i] == s[j] 时，考虑以下情况：
  • j - i == 0 ：即，只有一个字符，此时一定为回文子串，即， dp[i][j] = true
  • j - i == 1 ：即，只有 s[i] 和 s[j] 这两个相同的字符，此时也为回文子串，即， dp[i][j] = true
  • j - i > 1 ：即， s[i, j] 多于两个字符，此时，还需判断 s[i + 1, j - 1] 是否为回文子串。若 s[i + 1, j - 1] 是回文子串，则 s[i, j] 也是回文子串，否则， s[i, j] 不是回文子串。即， dp[i][j] = dp[i + 1][j - 1]

确定遍历顺序：根据递推公式知， dp[i][j] 依赖于 dp[i + 1][j - 1] ，因此，应按照从大到小的顺序遍历 i ，按照从小到大的顺序遍历 j

遍历结束后，dp 数组值为 true 的元素个数，即为字符串 s 的回文子串个数

代码实现：

int countSubstrings(string s) {
    vector<vector<bool>> dp(s.size(), vector<bool>(s.size(), false));
    int ans = 0;
    for (int i = s.size() - 1; i >= 0; i--) {
        for (int j = i; j < s.size(); j++) {
            if (s[i] == s[j]) {
                if (j - i <= 1 || dp[i + 1][j - 1]) {
                    dp[i][j] = true;
                    ans++;
                }
            }
        }
    }
    return ans;
}

时间复杂度：$O(n^2)$，其中 $n$ 是字符串 s 的长度

空间复杂度：$O(n^2)$

# LeetCode 674. 最长连续递增序列

674. Longest Continuous Increasing Subsequence

给定一个未经排序的整数数组，找到最长且 连续递增的子序列 ，并返回该序列的长度。

连续递增的子序列 可以由两个下标 l 和 r （ l < r ）确定，如果对于每个 l <= i < r ，都有 nums[i] < nums[i + 1] ，那么子序列 [nums[l], nums[l + 1], ..., nums[r - 1], nums[r]] 就是连续递增子序列。

示例 1：

输入：nums = [1,3,5,4,7]
输出：3
解释：最长连续递增序列是 [1,3,5] , 长度为 3

示例 2：

输入：nums = [2,2,2,2,2]
输出：1
解释：最长连续递增序列是 [2] , 长度为 1

提示：

• $1 \le$ nums.length $\le 10^4$
• $-10^9 \le$ nums[i] $\le 10^9$

# Method 1: 动态规划

算法思路：

定义 dp 数组： dp[i] 表示在 nums[0, i] 区间内，以 nums[i] 结尾的最长连续递增序列的长度

本题要求递增序列连续，因此，维护 dp[i] 只需比较 nums[i] 与 nums[i - 1] 即可，递归公式为： dp[i] = max(dp[i], dp[i - 1] + 1), i >= 1 && nums[i] > nums[i - 1]

遍历结束后，dp 数组的最大元素即为所求

代码实现：

int findLengthOfLCIS(vector<int>& nums) {
    int n = nums.size();
    vector<int> dp(n, 1); // dp[i] 表示以 nums[i] 结尾的最长连续递增序列的长度
    for (int i = 1; i < n; i++) {
        if (nums[i] > nums[i - 1]) // 连续递增
            dp[i] = max(dp[i], dp[i - 1] + 1);
    }
    int ans = 0;
    for (int i = 0; i < n; i++)
        ans = max(ans, dp[i]);
    return ans;
}

时间复杂度：$O(n)$ ，其中 $n$ 是数组的长度

空间复杂度：$O(n)$

# Method 2: 贪心

代码实现：

int findLengthOfLCIS(vector<int>& nums) {
    int n = nums.size();
    int ans = 0;
    int count = 1;
    for (int i = 1; i < n; i++) {
        if (nums[i] > nums[i - 1]) count++;
        else {
            ans = max(ans, count);
            count = 1;
        }
    }
    ans = max(ans, count); // 处理 nums[n - 1] > nums[n - 2] 的情况
    return ans;
}

时间复杂度：$O(n)$ ，其中 $n$ 是数组的长度

空间复杂度：$O(1)$

# LeetCode 70. 爬楼梯

LeetCode 70. Climbing Stairs

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

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

示例 1：

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

示例 2：

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

提示：

• $1 \le$ n $\le 45$

# Method 1: 动态规划

算法思路：

1. 确定 dp 数组及其含义： dp[i] 表示爬到第 i 阶的方案数

2. 确定递推公式：当 i >= 2 时， dp[i] = dp[i - 1] + dp[i - 2]

   • 可以从第 i - 1 阶爬 1 个台阶，到达第 i 阶，方案数为 dp[i - 1]
   • 也可以从第 i - 2 阶爬 2 个台阶，到达第 i 阶，方案数为 dp[i - 2]

3. 初始化 dp 数组： dp[1] = 1 ， dp[2] = 2

   • 爬到第 1 阶只有一种方案，因此， dp[1] = 1
   • 爬到第 2 阶有两种方案，因此， dp[2] = 2

4. 确定遍历顺序：根据递推公式可知， dp[i] 依赖于 dp[i - 1] 和 dp[i - 2] ，因此，应按 i 从小到大遍历

5. 举例推导 dp 数组

这里不考虑 dp[0] 的初始化，因为 dp[0] 并不具有实际含义

代码实现：

int climbStairs(int n) {
    if (n <= 1) return n;
    vector<int> dp(n + 1, 0);
    dp[1] = 1;
    dp[2] = 2;
    for (int i = 3; i <= n; i++)
        dp[i] = dp[i - 1] + dp[i - 2];
    return dp[n];
}

时间复杂度：$O(n)$

空间复杂度：$O(n)$

类似地，也可以利用滚动数组法来优化空间复杂度

# Method 2: 完全背包

算法思路：

每一步爬一个台阶，或者，每一步爬两个台阶，可以视为背包问题中的物品；楼梯的台阶数，可以视为背包问题中的背包容量

因此，问题可改写为：从 nums = {1, 2} 中选取若干个元素（每个元素可以重复选择），使得元素之和为 n ，一共有多少种方案？

即，问题是一个完全背包问题，并且，所要求的是选取元素的 排列 数

采用动态规划方法求解，其中，外层 for 循环遍历元素之和（背包容量），内层 for 循环遍历元素（物品），并且均按照从小到大的顺序遍历

代码实现：

int climbStairs(int n) {
    vector<int> nums = {1, 2};
    vector<int> dp(n + 1, 0);
    dp[0] = 1;
    for (int j = 1; j <= n; j++) {
        for (int num : nums) {
            if (j >= num)
                dp[j] += dp[j - num];
        }
    }
    return dp[n];
}

参考：代码随想录

# LeetCode 718. 最长重复子数组

718. Maximum Length of Repeated Subarray

给两个整数数组 nums1 和 nums2 ，返回 两个数组中 公共的 、长度最长的子数组的长度 。

示例 1：

输入：nums1 = [1,2,3,2,1], nums2 = [3,2,1,4,7]
输出：3
解释：长度最长的公共子数组是 [3,2,1]

示例 2：

输入：nums1 = [0,0,0,0,0], nums2 = [0,0,0,0,0]
输出：5

提示：

• $1 \le$ nums1.length , nums2.length $\le 1000$
• $0 \le$ nums1[i] , nums2[i] $\le 100$

# Method 1: 动态规划

# 实现一

定义 dp 数组： dp[i][j] 表示以 nums1[i] 与 nums2[j] 为结尾的最长重复子数组的长度，其中， 0 <= i < nums1.size() , 0 <= j < nums2.size()

• 若 nums1[i] != nums2[j] ，则 nums1[i] 与 nums2[j] 不可能作为重复子数组的末尾，即， dp[i][j] = 0
• 若 nums1[i] == nums2[j] ，则 nums1[i] 与 nums2[j] 可以作为重复子数组的末尾，即， dp[i][j] > 0

确定递推公式：若 num1[i] == nums2[j] ，则 dp[i][j] = dp[i - 1][j - 1] + 1

初始化：根据递推公式知，应初始化 dp[i][0] 与 dp[0][j]

• dp[i][0] ：若 nums1[i] == nums2[0] ，则 nums1[i] 可以与 nums2[0] 作为重复子数组，即， dp[i][0] = 1 ；否则， dp[i][0] = 0
• dp[0][j] ：若 nums1[0] == nums2[j] ，则 nums1[0] 可以与 nums2[j] 作为重复子数组，即， dp[0][j] = 1 ；否则， dp[0][j] = 0

遍历顺序：外层遍历 i 、内层遍历 j （可以交换）； i 与 j 均按照从小到大的顺序遍历

最后，从 dp 数组中找到最大值，即为最长重复子数组的长度

代码实现：

int findLength(vector<int>& nums1, vector<int>& nums2) {
    int m = nums1.size();
    int n = nums2.size();

    // 定义 dp 数组
    vector<vector<int>> dp(m, vector<int>(n, 0));

    // 初始化 dp 数组
    for (int i = 0; i < m; i++) {
        if (nums1[i] == nums2[0]) dp[i][0] = 1;
    }
    for (int j = 0; j < n; j++) {
        if (nums1[0] == nums2[j]) dp[0][j] = 1;
    }

    // 遍历
    for (int i = 1; i < m; i++) {
        for (int j = 1; j < n; j++) {
            if (nums1[i] == nums2[j])
                dp[i][j] = dp[i - 1][j - 1] + 1;
        }
    }

    // 寻找 dp 数组的最大元素
    int ans = 0;
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) {
            if (dp[i][j] > ans)
                ans = dp[i][j];
        }
    }

    return ans;
}

时间复杂度：$O(m \times n)$，其中 $m$ ，$n$ 分别是数组 nums1 、 nums2 的长度

空间复杂度：$O(m \times n)$

# 实现二

可以将 dp 数组定义为： dp[i][j] 表示以 nums1[i - 1] 与 nums2[j - 1] 为结尾的最长重复子数组的长度，其中， 0 <= i <= nums1.size() , 0 <= j <= nums2.size()

dp 数组的元素全部初始化为 0 即可

递推公式为：若 nums1[i - 1] == nums2[j - 1] ，则 dp[i][j] = dp[i - 1][j - 1] + 1

遍历顺序：与上一种实现相同， i 从 1 遍历至 nums1.size() ， j 从 1 遍历至 nums2.size()

代码实现：

int findLength(vector<int>& nums1, vector<int>& nums2) {
    int m = nums1.size();
    int n = nums2.size();
    int ans = 0;

    // 定义 dp 数组及其初始化
    vector<vector<int>> dp(m + 1, vector<int>(n + 1, 0));

    // 遍历
    for (int i = 1; i <= m; i++) {
        for (int j = 1; j <= n; j++) {
            if (nums1[i - 1] == nums2[j - 1])
                dp[i][j] = dp[i - 1][j - 1] + 1;
            if (dp[i][j] > ans)
                ans = dp[i][j];
        }
    }

    return ans;
}

# 优化

可以利用滚动数组的思想，将二维 dp 数组换成一维 dp 数组，即，一维数组的 dp[j] 对应上述二维数组的 dp[i][j] （实现二）

代码实现：

int findLength(vector<int>& nums1, vector<int>& nums2) {
    int m = nums1.size();
    int n = nums2.size();
    int ans = 0;
    vector<int> dp(n + 1, 0);
    for (int i = 1; i <= m; i++) {
        for (int j = n; j >= 1; j--) {
            if (nums1[i - 1] == nums2[j - 1]) dp[j] = dp[j - 1] + 1;
            else dp[j] = 0;           // nums1[i - 1] != nums2[j - 1] 时，dp[j] = 0
            ans = max(ans, dp[j]);
        }
    }
    return ans;
}

时间复杂度：$O(m \times n)$，其中 $m$ ，$n$ 分别是数组 nums1 、 nums2 的长度

空间复杂度：$O(n)$

参考：代码随想录

# LeetCode 72. 编辑距离

72. Edit Distance

给你两个单词 word1 和 word2， 请返回将 word1 转换成 word2 所使用的最少操作数 。

你可以对一个单词进行如下三种操作：

• 插入一个字符
• 删除一个字符
• 替换一个字符

示例 1：

输入：word1 = "horse", word2 = "ros"
输出：3
解释：
    horse -> rorse (将 'h' 替换为 'r')
    rorse -> rose (删除 'r')
    rose -> ros (删除 'e')

示例 2：

输入：word1 = "intention", word2 = "execution"
输出：5
解释：
    intention -> inention (删除 't')
    inention -> enention (将 'i' 替换为 'e')
    enention -> exention (将 'n' 替换为 'x')
    exention -> exection (将 'n' 替换为 'c')
    exection -> execution (插入 'u')

提示：

• $0 \le$ word1.length , word2.length $\le 500$
• word1 和 word2 由小写英文字母组成

# Method: 动态规划

算法思路：

定义 dp 数组： dp[i][j] 表示将 word1[0, i - 1] 转换成 word2[0, j - 1] 所需的最少操作数

初始化 dp[i][0] 与 dp[0][j] ：

• [dp][i][0] ：此时， word2[0, j - 1] 为空字符串，要将 word1[0, i - 1] 转换成空字符串，应将 word1[0, i - 1] 的全部字符都删除，即， dp[i][0] = i
• [dp][0][j] ：此时， word1[0, i - 1] 为空字符串，要将空字符串转换成 word2[0, j - 1] ，应将 word2[0, j - 1] 的全部字符都插入到 word1 ，即， dp[i][0] = j

推导 dp[i][j] 的状态转移过程：（要注意围绕 dp[i][j] 的定义进行思考）

• 当 word1[i - 1] == word2[j - 1] 时，无需操作 word1[i - 1] ，只需将 word1[0, i - 2] 转换成 word2[0, j - 2] ，因此， dp[i][j] = dp[i - 1][j - 1]
• 当 word1[i - 1] != word2[j - 1] 时，可针对 word1[0, i - 1] 进行 插入、删除、替换 三种操作：
  • 插入字符：在 word1[i - 2] 与 word1[i - 1] 之间插入一个字符，使之与 word2[j - 1] 相同。该操作 等价于 删除 word2[j - 1] ，因为插入字符和删除 word2[j - 1] 都能将 word1 变成 word2 。因此，所需的操作数为 1 + dp[i][j - 1] ，其中， 1 表示删除 word2[j - 1] 所需的操作数， dp[i][j - 1] 表示将 word1[0, i - 1] 转换成 word2[0, j - 2] 所需的最少操作数
  • 删除字符：删除 word1[i - 1] ，然后将 word1[0, i - 2] 转换成 word2[0, j - 1] 。所需的操作数为 1 + dp[i - 1][j]
  • 替换字符：将 word1[i - 1] 替换成与 word2[j - 1] 相同的字符，然后将 word1[0, i - 2] 转换成 word2[0, j - 2] 。所需的操作数为 1 + dp[i - 1][j - 1]
  • 综合以上三种情况，应取最小的操作数，即， dp[i][j] = min({1 + dp[i][j - 1], 1 + dp[i - 1][j], 1 + dp[i - 1][j - 1]})

遍历顺序：根据递推公式知， dp[i][j] 依赖于 dp[i - 1][j - 1] 、 dp[i - 1][j] 和 dp[i][j - 1] ，因此，应按照从左到右、从上到下的顺序维护 dp 数组，即，按照从小到大的顺序分别遍历 i 和 j

代码实现：

int minDistance(string word1, string word2) {
    int m = word1.size();
    int n = word2.size();
    vector<vector<int>> dp(m + 1, vector<int>(n + 1, 0));
    for (int i = 0; i <= m; i++) dp[i][0] = i;
    for (int j = 0; j <= n; j++) dp[0][j] = j;
    for (int i = 1; i <= m; i++) {
        for (int j = 1; j <= n; j++) {
            if (word1[i - 1] == word2[j - 1])
                dp[i][j] = dp[i - 1][j - 1];
            else
                dp[i][j] = min({dp[i][j - 1], dp[i - 1][j], dp[i - 1][j - 1]}) + 1;
        }
    }
    return dp[m][n];
}

时间复杂度：$O(m \times n)$ ，其中 $m$ 和 $n$ 分别是 word1 和 word2 的长度

空间复杂度：$O(m \times n)$

# LeetCode 746. 使用最小花费爬楼梯

LeetCode 746. Min Cost Climbing Stairs

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

你可以选择从下标为 0 或下标为 1 的台阶开始爬楼梯。

请你计算并返回达到楼梯顶部的最低花费。

示例 1：

输入：cost = [10,15,20]
输出：15
解释：你将从下标为 1 的台阶开始。
      - 支付 15 ，向上爬两个台阶，到达楼梯顶部。
      总花费为 15 。

示例 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 。

提示：

$2 \le$ cost.length $\le 1000$
$0 \le$ cost[i] $\le 999$

# Method: 动态规划

注意，楼梯顶部对应的是第 cost.size() 个台阶

算法思路：

1. 确定 dp 数组及其含义： vector<int> dp(cost.size() + 1, 0) ，其中， dp[i] 表示到达第 i 个台阶的最低费用

2. 确定递推公式： dp[i] = min(dp[i - 1] + cost[i - 1], dp[i - 2] + cost[i - 2])

   • 可以从第 i - 1 阶爬 1 个台阶到达第 i 阶，费用为 dp[i - 1] + cost[i - 1]
   • 也可以从第 i - 2 阶爬 2 个台阶到达第 i 阶，费用为 dp[i - 2] + cost[i - 2]
   • 综合两种情况，从中选择费用最低的，即， dp[i] = min(dp[i - 1] + cost[i - 1], dp[i - 2] + cost[i - 2])

3. 初始化 dp 数组： dp[0] = 0 ， dp[1] = 0

   • 第 0 个台阶和第 1 个台阶可以作为起点，因此，到达第 0 个台阶和第 1 个台阶的费用均为 0 ，即 dp[0] = dp[1] = 0

4. 确定遍历顺序：根据递推公式可知， dp[i] 依赖于 dp[i - 1] 和 dp[i - 2] ，因此，应按 i 从小到大遍历

5. 举例推导 dp 数组

最后， dp[cost.size()] 就是到达楼梯顶部的最低费用

代码实现：

int minCostClimbingStairs(vector<int>& cost) {
    int n = cost.size();
    vector<int> dp(n + 1, 0); // dp[i] 表示到达下标 i 的最低费用
    for (int i = 2; i <= n; i++) {
        dp[i] = min(dp[i - 1] + cost[i - 1], dp[i - 2] + cost[i - 2]);
    }
    return dp[n];
}

时间复杂度：$O(n)$

空间复杂度：$O(n)$