# 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) { // 区间内最后戳破的气球