hot100动态规划题解

发表于 2025/01/21 更新于 2025/01/21

作者 匆匆那年 43 分钟阅读

70. 爬楼梯

问题描述

假设你正在爬楼梯。需要 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 <= n <= 45

题解

这是一个经典的动态规划问题，类似于斐波那契数列。我们可以使用动态规划来解决。

题解

设 $d p [i]$ 表示爬到第 $i$ 阶的方法数：

如果只走一步，从第 $i - 1$ 阶到第 $i$ 阶，有 $d p [i - 1]$ 种方法。
如果走两步，从第 $i - 2$ 阶到第 $i$ 阶，有 $d p [i - 2]$ 种方法。

因此，状态转移方程为： $d p [i] = d p [i - 1] + d p [i - 2]$

初始条件：

$d p [1] = 1$ （只有一种方式爬到第一阶）
$d p [2] = 2$ （两种方式爬到第二阶： $1 + 1$ 或 $2$ ）

最后，返回 $d p [n]$ 即可。

优化

我们只需要维护两个变量来存储 $d p [i - 1]$ 和 $d p [i - 2]$ ，从而将空间复杂度优化为 $O (1)$ 。

C++ 实现

以下是优化后的实现：

  
#include <iostream>
using namespace std;

class Solution {
public:
    int climbStairs(int n) {
        if (n == 1) return 1;
        int prev2 = 1; // dp[1]
        int prev1 = 2; // dp[2]
        for (int i = 3; i <= n; ++i) {
            int current = prev1 + prev2;
            prev2 = prev1;
            prev1 = current;
        }
        return prev1;
    }
};

int main() {
    Solution solution;
    int n = 5; // 示例测试
    cout << "爬楼梯方法数: " << solution.climbStairs(n) << endl;
    return 0;
}

复杂度分析

时间复杂度： $O (n)$ ，需要遍历从 3 到 $n$ 的所有阶数。
空间复杂度： $O (1)$ ，只使用了两个额外变量。

示例运行

输入：n = 5

输出：8 解释：方法数为 1+1+1+1+1,2+1+1+1,1+2+1+1,1+1+2+1,1+1+1+2,2+2+1,2+1+2,1+2+21+1+1+1+1, 2+1+1+1, 1+2+1+1, 1+1+2+1, 1+1+1+2, 2+2+1, 2+1+2, 1+2+2。

118. 杨辉三角

问题描述

给定一个非负整数 numRows，生成「杨辉三角」的前 numRows 行。

在「杨辉三角」中，每个数是它左上方和右上方的数的和。

示例 1:

输入: numRows = 5
输出: [[1],[1,1],[1,2,1],[1,3,3,1],[1,4,6,4,1]]

示例 2:

输入: numRows = 1
输出: [[1]]

提示:

1 <= numRows <= 30

题解

这是一个经典的二维动态规划问题。每一行中的每个元素是上一行对应位置元素的和，即：

题解思路

每行的第一个和最后一个元素始终是 1。
其他元素由上一行的两个相邻元素之和计算得出。
- 对于第 $i$ 行的第 $j$ 个元素： $t r i a n g l e [i] [j] = t r i a n g l e [i - 1] [j - 1] + t r i a n g l e [i - 1] [j]$

实现步骤

初始化结果容器，构造每一行的初始值。
对于每一行，从第 $1$ 列到倒数第 $2$ 列进行元素填充。
返回最终结果。

C++ 实现

以下是具体实现：

  
#include <iostream>
#include <vector>
using namespace std;

class Solution {
public:
    vector<vector<int>> generate(int numRows) {
        vector<vector<int>> triangle(numRows);

        for (int i = 0; i < numRows; ++i) {
            // 每行的大小为 i+1，所有元素初始化为 1
            triangle[i] = vector<int>(i + 1, 1);

            // 填充非边界元素
            for (int j = 1; j < i; ++j) {
                triangle[i][j] = triangle[i-1][j-1] + triangle[i-1][j];
            }
        }

        return triangle;
    }
};

int main() {
    Solution solution;
    int numRows = 5; // 示例测试
    vector<vector<int>> result = solution.generate(numRows);

    // 输出结果
    for (const auto& row : result) {
        for (int val : row) {
            cout << val << " ";
        }
        cout << endl;
    }

    return 0;
}

复杂度分析

时间复杂度： $O (n^{2})$ ，需要计算每个元素的值，总共 $\frac{n (n + 1)}{2}$ 个元素。
空间复杂度： $O (n^{2})$ ，存储整个杨辉三角。

示例运行

输入：numRows = 5

输出：

扩展

如果你只需要第 k 行的结果，可以进一步优化为 $O (k)$ 空间复杂度的解法，通过滚动数组实现。

198. 打家劫舍

问题描述

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

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

示例 1：

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

示例 2：

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

提示：

1 <= nums.length <= 100
0 <= nums[i] <= 400

题解

这是一个经典的动态规划问题，目标是找到不相邻元素的最大子集和。

题解思路

设数组 nums 的长度为 $n$ 。定义一个数组 $d p [i]$ 表示 偷窃前 $i$ 间房屋能够获得的最大金额：

状态转移方程：
$d p [i] = max (d p [i - 1], d p [i - 2] + n u m s [i])$
- $d p [i - 1]$ ：不偷第 $i$ 间房，直接继承前面的最大值。
- $d p [i - 2] + n u m s [i]$ ：偷第 $i$ 间房，累计金额为两间隔房的最大值加当前房间金额。
边界条件：
- $d p [0] = 0$ ：没有房间可偷，金额为 0。
- $d p [1] = n u m s [0]$ ：只有一间房时，偷这一间房。
最后返回 $d p [n]$ 。

空间优化

由于状态转移方程仅依赖 $d p [i - 1] 和 d p [i - 2]$ ，可以用两个变量代替数组，将空间复杂度从 $O (n)$ 优化为 $O (1)$ 。

C++ 实现

以下是空间优化后的代码：

  
#include <iostream>
#include <vector>
using namespace std;

class Solution {
public:
    int rob(vector<int>& nums) {
        if (nums.empty()) return 0;
        if (nums.size() == 1) return nums[0];

        int prev2 = 0; // dp[i-2]
        int prev1 = 0; // dp[i-1]
        for (int num : nums) {
            int current = max(prev1, prev2 + num); // dp[i]
            prev2 = prev1; // 更新 dp[i-2]
            prev1 = current; // 更新 dp[i-1]
        }
        return prev1;
    }
};

int main() {
    Solution solution;
    vector<int> nums = {2, 7, 9, 3, 1}; // 示例测试
    cout << "能偷窃的最大金额: " << solution.rob(nums) << endl;
    return 0;
}

复杂度分析

时间复杂度： $O (n)$ ，遍历一遍数组。
空间复杂度： $O (1)$ ，只使用了两个变量。

示例运行

输入：nums = [2,7,9,3,1]

输出：12

扩展

如果题目限制房屋构成一个环形（第一个和最后一个房屋相邻），可以将问题分解为两次线性处理：

选择偷第 1 间房，排除最后一间。
选择偷最后一间房，排除第 1 间。
返回上述两种情况的最大值。

279. 完全平方数

问题描述

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

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

示例 1：

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

示例 2：

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

提示：

$1 <= n <= 10^{4}$

题解

这是一个典型的动态规划问题，可以通过求解「完全平方数」的最小组合来实现。

题解思路

动态规划定义：
- 定义 $d p [i]$ 表示组成整数 $i$ 所需的最少完全平方数的数量。
状态转移方程：
- 对于每个整数 $i$ ，枚举所有小于等于 $i$ 的完全平方数 $j^{2}$ ： $d p [i] = min (d p [i], d p [i - j^{2}] + 1)$ 其中 $j^{2} \leq i$ 。
边界条件：
- $d p [0] = 0$ ：组成整数 0 所需的完全平方数数量为 0。
结果：
- 最终 $d p [n]$ 即为答案。

C++ 实现

  
#include <iostream>
#include <vector>
#include <cmath>
using namespace std;

class Solution {
public:
    int numSquares(int n) {
        vector<int> dp(n + 1, INT_MAX);
        dp[0] = 0;

        for (int i = 1; i <= n; ++i) {
            for (int j = 1; j * j <= i; ++j) {
                dp[i] = min(dp[i], dp[i - j * j] + 1);
            }
        }

        return dp[n];
    }
};

int main() {
    Solution solution;
    int n = 12; // 示例测试
    cout << "最少完全平方数数量: " << solution.numSquares(n) << endl;
    return 0;
}

复杂度分析

时间复杂度：
- 外层循环遍历 $n$ 次，内层循环遍历小于 $\sqrt{n}$ 的所有平方数。
- 总时间复杂度为 $O (n \sqrt{n})$ 。
空间复杂度：
- 使用一个大小为 $n + 1$ 的数组存储中间结果，空间复杂度为 $O (n)$ 。

示例运行

输入：

n = 12

输出：

3

解释：12 可以分解为 $4 + 4 + 4$ 。

扩展优化

如果 $n$ 很大，想进一步优化时间复杂度，可以使用 四平方和定理 或 贪心枚举法：

四平方和定理：任何正整数都可以表示为最多四个平方数的和。
贪心枚举：从小到大验证是否可以由 kk 个平方数组成。

322. 零钱兑换

问题描述

给你一个整数数组 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 <= coins.length <= 12
$1 <= c o i n s [i] <= 2^{31} - 1$
$0 <= a m o u n t <= 10^{4}$

题解

题解思路

这是一个经典的动态规划问题，用来求解「最优子结构」问题。

动态规划方法

定义状态：
- 用 $d p [i]$ 表示凑成金额 $i$ 所需的最少硬币个数。
- 如果无法凑成 $i$ ，设 $d p [i] = \infty$ 。
状态转移方程：
- 对于每个金额 $i$ 和硬币面额 $c$ ： $d p [i] = min (d p [i], d p [i - c] + 1)$ 其中 $c$ 是小于等于 $i$ 的硬币面额。
边界条件：
- $d p [0] = 0$ ：凑成金额 $0$ 需要 $0$ 个硬币。
结果：
- 如果 $d p [a m o u n t] = \infty$ ，返回 -1；否则返回 $d p [a m o u n t]$ 。

C++ 实现

  
#include <iostream>
#include <vector>
#include <algorithm>
#include <climits>
using namespace std;

class Solution {
public:
    int coinChange(vector<int>& coins, int amount) {
        vector<int> dp(amount + 1, INT_MAX);
        dp[0] = 0; // 凑成金额 0 需要 0 个硬币

        for (int i = 1; i <= amount; ++i) {
            for (int coin : coins) {
                if (i >= coin && dp[i - coin] != INT_MAX) {
                    dp[i] = min(dp[i], dp[i - coin] + 1);
                }
            }
        }

        return dp[amount] == INT_MAX ? -1 : dp[amount];
    }
};

int main() {
    Solution solution;
    vector<int> coins = {1, 2, 5};
    int amount = 11;
    cout << "最少硬币数量: " << solution.coinChange(coins, amount) << endl;
    return 0;
}

复杂度分析

时间复杂度：
- 外层循环遍历金额 $a m o u n t$ ，内层循环遍历硬币种类 $k$ 。
- 总时间复杂度为 $O (k \cdot a m o u n t)$ 。
空间复杂度：
- 使用了一个大小为 $a m o u n t + 1$ 的数组，空间复杂度为 $O (a m o u n t)$ 。

示例运行

输入：

  
coins = [1, 2, 5], amount = 11

输出：

3

解释：11=5+5+111 = 5 + 5 + 1。

特殊情况

没有可用硬币：
- 如果 coins 为空，直接返回 -1。
金额为 0：
- 如果 amount = 0，直接返回 0。
无法凑成金额：
- 如果所有硬币面额都大于 amount，返回 -1。

这套动态规划解法兼顾效率和简洁性，是处理这类最优化问题的标准方法。

139. 单词拆分

问题描述

给你一个字符串 s 和一个字符串列表 wordDict 作为字典。如果可以利用字典中出现的一个或多个单词拼接出 s 则返回 true。

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

示例 1：

输入: s = "leetcode", wordDict = ["leet", "code"]
输出: true
解释: 返回 true 因为 "leetcode" 可以由 "leet" 和 "code" 拼接成。

示例 2：

输入: s = "applepenapple", wordDict = ["apple", "pen"]
输出: true
解释: 返回 true 因为 "applepenapple" 可以由 "apple" "pen" "apple" 拼接成。
     注意，你可以重复使用字典中的单词。

示例 3：

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

提示：

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

题解

这是一个经典的动态规划问题，目标是判断字符串是否可以用字典中的单词组成。

动态规划解法

定义状态：
- 定义 $d p [i]$ 为布尔值，表示字符串 $s [0 : i]$ 是否可以被字典单词拼接而成。
- 如果 $d p [n] = true$ ，说明字符串 $s$ 可以由字典单词组成。
状态转移方程：
- 对于每个 $i$ ，检查所有可能的分割点 $j$ ： $d p [i] = d p [j] \land (s [j : i] \in wordDict)$
- 如果 $s [j : i]$ 在字典中，且 $d p [j] = true$ ，则 $d p [i] = true$ 。
初始化：
- $d p [0] = true$ ，因为空字符串可以用字典组成。
结果：
- 返回 $d p [n]$ ，其中 $n$ 是字符串 $s$ 的长度。

C++ 实现

  
#include <iostream>
#include <vector>
#include <string>
#include <unordered_set>
using namespace std;

class Solution {
public:
    bool wordBreak(string s, vector<string>& wordDict) {
        unordered_set<string> wordSet(wordDict.begin(), wordDict.end());
        int n = s.size();
        vector<bool> dp(n + 1, false);
        dp[0] = true;

        for (int i = 1; i <= n; ++i) {
            for (int j = 0; j < i; ++j) {
                if (dp[j] && wordSet.find(s.substr(j, i - j)) != wordSet.end()) {
                    dp[i] = true;
                    break;
                }
            }
        }

        return dp[n];
    }
};

int main() {
    Solution solution;
    string s = "leetcode";
    vector<string> wordDict = {"leet", "code"};
    cout << (solution.wordBreak(s, wordDict) ? "true" : "false") << endl;
    return 0;
}

复杂度分析

时间复杂度：
- 外层循环遍历字符串 $s$ ，时间复杂度为 $O (n)$ 。
- 内层循环检查每个分割点，最多需要 $O (n)$ 次。
- 子字符串查找操作 $s . s u b s t r (j, i - j)$ 需要 $O (k)$ 的时间，其中 $k$ 是子字符串长度（均摊为 $O (1)$ ）。
- 总复杂度为 $O (n^{2})$ 。
空间复杂度：
- 使用了一个大小为 $n + 1$ 的数组 $d p$ 和一个哈希表，空间复杂度为 $O (n + m)$ ，其中 $m$ 是字典的总单词长度。

示例运行

输入：

  
s = "leetcode"
wordDict = ["leet", "code"]

输出：

true

优化

如果字典中的单词长度较小，可以限制 $j$ 的范围为 $[i - maxWordLen, i]$ ，其中 $maxWordLen$ 是字典中最长单词的长度。这将减少循环次数，提高效率。

300. 最长递增子序列

问题描述

给你一个整数数组 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 <= nums.length <= 2500
$- 10^{4} <= n u m s [i] <= 10^{4}$

进阶：

你能将算法的时间复杂度降低到 O(n log(n)) 吗?

题解

解题思路

这是一个经典的动态规划和二分查找问题。

方法 1：动态规划 $O (n^{2})$

定义状态：
- $d p [i]$ 表示以 $n u m s [i]$ 结尾的最长递增子序列的长度。
状态转移方程：
- 对于每个 $i$ ，检查所有比 $n u m s [i]$ 小的元素 $n u m s [j]$ ： $d p [i] = max (d p [i], d p [j] + 1) if n u m s [j] < n u m s [i]$
初始化：
- 每个位置的初始值为 1（单个元素构成的子序列）。
结果：
- 返回 dpdp 中的最大值。

C++ 实现

  
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

class Solution {
public:
    int lengthOfLIS(vector<int>& nums) {
        int n = nums.size();
        vector<int> dp(n, 1); // 每个元素最小长度为 1
        int maxLength = 1;

        for (int i = 1; i < n; ++i) {
            for (int j = 0; j < i; ++j) {
                if (nums[j] < nums[i]) {
                    dp[i] = max(dp[i], dp[j] + 1);
                }
            }
            maxLength = max(maxLength, dp[i]);
        }

        return maxLength;
    }
};

int main() {
    Solution solution;
    vector<int> nums = {10, 9, 2, 5, 3, 7, 101, 18};
    cout << "最长递增子序列长度: " << solution.lengthOfLIS(nums) << endl;
    return 0;
}

时间复杂度： $O (n^{2})$ ，两层循环。
空间复杂度： $O (n)$ ，用于存储 $d p$ 数组。

方法 2：动态规划 + 二分查找 $O (n \log n)$

维护一个数组 sub：
- sub 是一个动态数组，用来存储当前递增子序列的末尾元素。
- 它不一定是真正的递增子序列，但长度与最长递增子序列的长度一致。
操作逻辑：
- 遍历 $n u m s$ ，对于每个元素 $n u m$ ：
  - 如果 $n u m$ 大于 sub 的最后一个元素，则将 $n u m$ 添加到 sub。
  - 否则，用二分查找找到 sub 中第一个大于等于 $n u m$ 的元素，并将其替换为 $n u m$ 。
最终结果：
- sub 的长度即为最长递增子序列的长度。

C++ 实现

  
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

class Solution {
public:
    int lengthOfLIS(vector<int>& nums) {
        vector<int> sub;
        for (int num : nums) {
            auto it = lower_bound(sub.begin(), sub.end(), num); // 二分查找位置
            if (it == sub.end()) {
                sub.push_back(num); // 如果 num 比所有元素都大，添加到末尾
            } else {
                *it = num; // 否则替换第一个大于等于 num 的元素
            }
        }
        return sub.size();
    }
};

int main() {
    Solution solution;
    vector<int> nums = {10, 9, 2, 5, 3, 7, 101, 18};
    cout << "最长递增子序列长度: " << solution.lengthOfLIS(nums) << endl;
    return 0;
}

时间复杂度： $O (n \log n)$ ，每次二分查找 $O (\log n)$ ，总共 $n$ 次。
空间复杂度： $O (n)$ ，用于存储 sub 数组。

示例运行

输入：

  
nums = [10, 9, 2, 5, 3, 7, 101, 18]

输出：

4

解释：最长递增子序列是 [2, 3, 7, 101]。

总结

方法 1（动态规划）适用于数据规模较小的情况。
方法 2（动态规划 + 二分查找）更高效，适用于数据规模较大的情况。

152. 乘积最大子数组

问题描述

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

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

示例 1:

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

示例 2:

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

提示:

$1 <= n u m s . l e n g t h <= 2 * 10^{4}$
-10 <= nums[i] <= 10
nums 的任何子数组的乘积都保证是一个 32-位 整数

题解

解题思路

乘积最大子数组问题可以通过动态规划解决，主要需要同时维护当前子数组的最大值和最小值，因为负数的乘积可能会将最小值变为最大值。

动态规划方法

定义状态：
- $maxProd [i]$ ：表示以 $n u m s [i]$ 结尾的子数组的最大乘积。
- $minProd [i]$ ：表示以 $n u m s [i]$ 结尾的子数组的最小乘积。
状态转移方程：
- 如果 $n u m s [i]$ 是正数： $maxProd [i] = max (maxProd [i - 1] \times n u m s [i], n u m s [i])$
  $minProd [i] = min (minProd [i - 1] \times n u m s [i], n u m s [i])$
- 如果 $n u m s [i]$ 是负数，最大值和最小值需要交换： $maxProd [i] = max (minProd [i - 1] \times n u m s [i], n u m s [i])$
  $minProd [i] = min (maxProd [i - 1] \times n u m s [i], n u m s [i])$
初始化：
- $maxProd [0] = minProd [0] = n u m s [0]$ 。
- 初始化全局最大值为 $maxProd [0]$ 。
结果：
- 返回 $maxProd$ 数组中的最大值。

空间优化

由于 $maxProd [i]$ 和 $minProd [i]$ 只依赖于上一状态，可以使用两个变量替代数组，优化空间复杂度。

C++ 实现

  
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

class Solution {
public:
    int maxProduct(vector<int>& nums) {
        if (nums.empty()) return 0;

        int maxProd = nums[0];
        int minProd = nums[0];
        int result = nums[0];

        for (int i = 1; i < nums.size(); ++i) {
            if (nums[i] < 0) {
                swap(maxProd, minProd); // 交换最大值和最小值
            }
            maxProd = max(nums[i], maxProd * nums[i]);
            minProd = min(nums[i], minProd * nums[i]);

            result = max(result, maxProd);
        }

        return result;
    }
};

int main() {
    Solution solution;
    vector<int> nums = {2, 3, -2, 4}; // 示例测试
    cout << "最大子数组乘积: " << solution.maxProduct(nums) << endl;
    return 0;
}

复杂度分析

时间复杂度：
$O (n)$
- 遍历数组一次，每次计算当前的最大值和最小值。
空间复杂度：
$O (1)$
- 使用常数空间保存当前的最大值、最小值和最终结果。

示例运行

输入：

  
nums = [2, 3, -2, 4]

输出：

6

解释：子数组 [2,3] 的乘积最大，为 6。

注意事项

当数组包含负数时，最大值和最小值的交替变化需要特别注意。
如果数组中有 $0$ ，会导致乘积归零，因此需要重新开始计算。

总结

动态规划解法能够高效解决这类问题。
空间优化版利用滚动变量降低了空间复杂度，非常适合大规模输入的情况。

416. 分割等和子集

问题描述

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

示例 1：

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

示例 2：

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

提示：

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

题解

这是一个典型的 动态规划问题，可以通过背包问题的变种来解决。问题要求将一个数组分成两个子集，使得它们的和相等。

思路

总和判断：首先计算数组的总和 sum。如果 sum 是奇数，那么直接返回 false，因为一个奇数无法被平分成两个整数相等的部分。
子集和问题：如果 sum 是偶数，目标是找到一个子集，它的和是 sum / 2。这个问题转换成了一个典型的背包问题，要求在给定的数组中找到一个子集，使得它的和等于 sum / 2。
动态规划：使用动态规划来判断是否能从数组中选择一些元素，使得这些元素的和等于 sum / 2。

动态规划步骤

初始化一个布尔数组 dp，其中 dp[i] 表示是否能从数组中选择一些元素，使得它们的和等于 i。
初始化时，dp[0] = true，因为总是可以选择一个空集来达到和为 0。
对于每个数字 num，从 sum / 2 到 num 遍历更新 dp[i]，如果 dp[i - num] 为 true，则将 dp[i] 设置为 true。

代码实现

  
#include <vector>
#include <numeric>
using namespace std;

bool canPartition(vector<int>& nums) {
    int sum = accumulate(nums.begin(), nums.end(), 0);
    
    // 如果总和是奇数，不可能分成两部分
    if (sum % 2 != 0) {
        return false;
    }
    
    int target = sum / 2;
    vector<bool> dp(target + 1, false);
    dp[0] = true;  // 和为0时，表示可以选择空集
    
    // 遍历每个数
    for (int num : nums) {
        // 从后向前更新dp数组
        for (int i = target; i >= num; --i) {
            dp[i] = dp[i] || dp[i - num];
        }
    }
    
    return dp[target];  // 如果dp[target]为true，说明可以分割成两个和相等的子集
}

解释

总和计算：我们首先计算整个数组的和 sum。如果 sum 是奇数，直接返回 false。
目标和：我们设定一个目标和 target = sum / 2，然后尝试找到是否有子集的和等于 target。
动态规划：我们使用一个一维布尔数组 dp 来记录是否可以通过选择一些元素的和达到某个值 i。每次遍历一个数时，从后向前更新 dp 数组，确保每个数只能被使用一次。

复杂度分析

时间复杂度：O(n * target)，其中 n 是数组 nums 的长度，target 是 sum / 2。由于每个元素都会更新 dp 数组，时间复杂度是 n * target。
空间复杂度：O(target)，我们只需要一个一维数组来记录子集和的情况。

示例

示例 1：

  
vector<int> nums = {1, 5, 11, 5};
cout << canPartition(nums) << endl;  // 输出 true

示例 2：

  
vector<int> nums = {1, 2, 3, 5};
cout << canPartition(nums) << endl;  // 输出 false

通过这种方式，我们可以高效地判断一个数组是否能分割成两个和相等的子集。

32. 最长有效括号

问题描述

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

示例 1：

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

示例 2：

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

示例 3：

输入：s = ""
输出：0

提示：

$0 <= s . l e n g t h <= 3 * 10^{4}$
s[i] 为 '(' 或 ')'s

题解

这个问题要求我们找出给定字符串中最长有效括号子串的长度。有效括号是指每个 '(' 都有一个匹配的 ')'，并且它们是连续的。

思路

我们可以使用栈或者 动态规划 两种方法来解决这个问题。以下是这两种方法的详细讲解。

方法 1：使用栈

栈的方法非常直观，它可以帮助我们记录括号的匹配情况。

步骤

初始化栈：我们使用一个栈来存储括号的索引。栈的作用是帮助我们跟踪当前未匹配的括号位置。初始时，可以将栈的第一个元素设为 -1，用于处理边界条件。
遍历字符串：对于每个字符：
- 如果是 '('，将其索引压入栈中。
- 如果是 ')'，检查栈顶元素。如果栈顶是 '('，表示找到了一个有效的括号对，弹出栈顶元素，计算当前有效括号的长度。此时栈顶的元素表示未匹配括号的索引，计算当前有效括号的长度为当前索引减去栈顶元素的索引。
更新最长有效括号长度：每次计算出有效括号的长度后，更新最长有效括号的长度。

代码实现

  
#include <vector>
#include <algorithm>
using namespace std;

int longestValidParentheses(string s) {
    stack<int> stk;
    stk.push(-1);  // 用于处理边界情况
    int max_len = 0;

    for (int i = 0; i < s.size(); i++) {
        if (s[i] == '(') {
            stk.push(i);  // 入栈当前索引
        } else {
            stk.pop();  // 弹出栈顶
            if (!stk.empty()) {
                max_len = max(max_len, i - stk.top());  // 更新最长有效括号长度
            } else {
                stk.push(i);  // 如果栈为空，推入当前索引
            }
        }
    }
    
    return max_len;
}

解释

栈操作：栈用于跟踪括号的索引。对于 '('，我们将其索引压入栈中；对于 ')'，我们弹出栈顶元素，计算有效括号的长度。
计算长度：每次弹出栈顶元素后，栈顶的元素是一个未匹配括号的索引，当前有效括号的长度为当前索引减去栈顶元素的索引。

方法 2：使用动态规划

动态规划的思路是通过记录每个位置的最长有效括号长度来构建解。

步骤

定义状态：我们定义一个数组 dp，其中 dp[i] 表示以索引 i 结尾的最长有效括号的长度。
状态转移：
- 如果 s[i] 是 ')'，我们判断 s[i-1] 是否是 '('，如果是，则 dp[i] = dp[i-2] + 2。
- 如果 s[i-1] 是 ')'，我们需要检查 dp[i - dp[i-1] - 1]，如果这个位置是 '('，则可以将 dp[i] = dp[i-1] + 2 + dp[i - dp[i-1] - 2]。
更新最大值：每次更新 dp[i] 时，我们也更新 max_len。

代码实现

  
#include <vector>
#include <algorithm>
using namespace std;

int longestValidParentheses(string s) {
    int n = s.size();
    vector<int> dp(n, 0);
    int max_len = 0;

    for (int i = 1; i < n; i++) {
        if (s[i] == ')') {
            if (s[i - 1] == '(') {
                dp[i] = (i >= 2 ? dp[i - 2] : 0) + 2;
            } else if (i - dp[i - 1] - 1 >= 0 && s[i - dp[i - 1] - 1] == '(') {
                dp[i] = dp[i - 1] + 2 + (i - dp[i - 1] - 2 >= 0 ? dp[i - dp[i - 1] - 2] : 0);
            }
            max_len = max(max_len, dp[i]);
        }
    }

    return max_len;
}

解释

状态定义：dp[i] 表示以 i 为结尾的最长有效括号长度。
状态转移：如果 s[i] 是 ')'，我们通过检查 s[i-1] 和 s[i - dp[i-1] - 1] 来更新 dp[i] 的值。
更新最大值：每次计算 dp[i] 后，我们都更新 max_len。

复杂度分析

时间复杂度：O(n)，因为我们只遍历一次字符串。
空间复杂度：O(n)，我们需要一个额外的 dp 数组来存储每个位置的有效括号长度。

示例

示例 1：

  
string s = "(()";
cout << longestValidParentheses(s) << endl;  // 输出 2

示例 2：

  
string s = ")()())";
cout << longestValidParentheses(s) << endl;  // 输出 4

示例 3：

  
string s = "";
cout << longestValidParentheses(s) << endl;  // 输出 0

总结

栈方法：简单直观，空间复杂度较低 O(n)。
动态规划方法：更为灵活，但空间复杂度较高，适用于需要逐步构建解的情况。

leetcode, hot100

本文由作者按照 CC BY 4.0 进行授权

70. 爬楼梯

问题描述

题解

题解

优化

C++ 实现

复杂度分析

示例运行

118. 杨辉三角

问题描述

题解

题解思路

C++ 实现

复杂度分析

示例运行

扩展

198. 打家劫舍

问题描述

题解

题解思路

空间优化

C++ 实现

复杂度分析

示例运行

扩展

279. 完全平方数

问题描述

题解

题解思路

C++ 实现

复杂度分析

示例运行

输入：

输出：

扩展优化

322. 零钱兑换

问题描述

题解

题解思路

动态规划方法

C++ 实现

复杂度分析

示例运行

输入：

输出：

特殊情况

139. 单词拆分

问题描述

题解

动态规划解法

C++ 实现

复杂度分析

示例运行

输入：

输出：

优化

300. 最长递增子序列

问题描述

题解

解题思路

方法 1：动态规划 O(n2)

C++ 实现

方法 2：动态规划 + 二分查找 O(nlog⁡n)

C++ 实现

示例运行

输入：

输出：

总结

152. 乘积最大子数组

问题描述

题解

解题思路

动态规划方法

空间优化

C++ 实现

复杂度分析

示例运行

输入：

输出：

注意事项

方法 1：动态规划 $O (n^{2})$

方法 2：动态规划 + 二分查找 $O (n \log n)$