Leedcode刷题——6 动态规划（DP问题）

注：以下代码均为c++

1. 最大子数组和

思路：

int maxSubArray(vector<int>& nums) {
    int res = INT_MIN, f = 0;
    for(int i = 0; i < nums.size(); i++){
        f = max(f, 0) + nums[i];
        res = max(f, res);
    }
    return res;
}
1
2
3
4
5
6
7
8

2. 三角形最小路径和

思路：

法1：用nxn的二维数组记录已经求过的结果

int minimumTotal(vector<vector<int>>& triangle){
    int n = triangle.size();
    vector<vector<int>> f(n,vector<int>(n));  //高维vector初始化：nxn的二维数组
    f[0][0] = triangle[0][0];
    for(int i = 1; i < n; i++){
        for(int j = 0; j <= i; j++){
            if(j-1 >= 0  && j < i)
                f[i][j] = min(f[i-1][j-1], f[i-1][j]) + triangle[i][j];
            else if(j-1 < 0)
                f[i][j] = f[i-1][j] + triangle[i][j];
            else
                f[i][j] = f[i-1][j-1] + triangle[i][j];
        }
    }
    int mins = INT_MAX;
    for(int i = 0; i < n; i++){
        mins = min(mins, f[n-1][i]);
    }
    return mins;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

法2：优化：用2xn的二维数组（只记录上一层结果）记录已经求过的结果

int minimumTotal(vector<vector<int>>& triangle){
    int n = triangle.size();
    vector<vector<int>> f(2,vector<int>(n));  //优化：由于只需要记录上一层的结果，所以开两层数组即可。
    f[0][0] = triangle[0][0];
    for(int i = 1; i < n; i++){
        for(int j = 0; j <= i; j++){
            if(j-1 >= 0  && j < i)
                f[i & 1][j] = min(f[i-1 & 1][j-1], f[i-1 & 1][j]) + triangle[i][j];  //n%2相当于&1
            else if(j-1 < 0)
                f[i & 1][j] = f[i-1 & 1][j] + triangle[i][j];
            else
                f[i & 1][j] = f[i-1 & 1][j-1] + triangle[i][j];
        }
    }
    int mins = INT_MAX;
    for(int i = 0; i < n; i++){
        mins = min(mins, f[n-1 & 1][i]);
    }
    return mins;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

3. 不同路径2

思路：
状态表示：f[i][j]：当前路径的数量
状态计算：f[i][j] = f[i-1][j] + f[i][j-1]

下面的代码一个是我自己写的，一个是答案，思路是一样的，但是答案写的更简便一些。

//我自己写的代码
int uniquePathsWithObstacles(vector<vector<int>>& obstacleGrid) {
    int m = obstacleGrid.size(), n = obstacleGrid[0].size();
    vector<vector<int>> f(m, vector<int>(n));
    for(int i = 0; i < m; i++){
        for(int j = 0; j < n; j++){
            if(obstacleGrid[i][j])  //如果是障碍物，跳过
                continue;
            if(i-1 >= 0  && j-1 >= 0)
                f[i][j] = f[i-1][j] + f[i][j-1];
            else if(i == 0 && j-1 >= 0)
                f[i][j] = f[i][j-1];
            else if(j == 0 && i-1 >=0)
                f[i][j] = f[i-1][j];
            else  //如果是左上角，赋值为1
                f[i][j] = 1;
        }
    }
    return f[m-1][n-1];
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

//答案（感觉他写的更简便）
int uniquePathsWithObstacles(vector<vector<int>>& obstacleGrid) {
    int m = obstacleGrid.size(), n = obstacleGrid[0].size();
    vector<vector<int>> f(m, vector<int>(n));
    for(int i = 0; i < m; i++){
        for(int j = 0; j < n; j++){
            if(obstacleGrid[i][j])  //如果是障碍物，跳过
                continue;
            if(i == 0 && j == 0)    f[i][j] = 1;  //如果是左上角
            if(i > 0)   f[i][j] += f[i-1][j];  //如果不是第一行
            if(j > 0)   f[i][j] += f[i][j-1];  //如果不是第一列
        }
    }
    return f[m-1][n-1];
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

4. 解码方法

思路：

int numDecodings(string s) {
    int n = s.size();
    vector<int> f(n);
    //n=1，直接返回
    if(n == 1){
        if(s[0] == '0')   return 0;
        else    return 1;
    }
    //给f[0]f[1]赋值
    if(s[0] == '0')
        f[0] = 0, f[1] = 0;
    else{
        f[0] = 1;
        int num = (s[0]-'0')*10 + s[1] - '0';
        if(s[1] == '0'){
            if(num >= 1 && num <= 26)   f[1] = 1;
            else    f[1] = 0;
        }
        else{
            if(num >= 1 && num <= 26)   f[1] = 2;
            else    f[1] = 1;
        }
    }
    //动态规划
    for(int i = 2; i < n; i++){
        if(s[i] != '0')  f[i] += f[i-1];
        int num = (s[i-1]-'0')*10 + s[i] - '0';
        if(num >= 10 && num <= 26)   f[i] += f[i-2];  //注意这里是num>=10不是num>=1，因为s[i-1] != '0'
    }
    return f[n-1];
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31

5. 打家劫舍

思路：
状态表示：偷窃到第i家，偷窃的最高金额 f[i]
状态计算：f[i] = max(f[i-2], f[i-3]) + nums[i]

int rob(vector<int>& nums) {
    int n = nums.size();
    vector<int> f(n);
    if(n == 1)  return nums[0];
    if(n == 2)  return max(nums[0], nums[1]);
    if(n == 3)  return max(nums[0] + nums[2], nums[1]);

    f[0] = nums[0];
    f[1] = max(nums[0], nums[1]);
    f[2] = max(nums[0] + nums[2], nums[1]);
    for(int i = 3; i < n; i++){
        f[i] = max(f[i-2], f[i-3]) + nums[i];
    }
    return max(f[n-1], f[n-2]);
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

6. 最长递增子序列

思路：
状态表示：f[i] 当前最长递归子序列的长度
状态计算：当前最长递增子序列的长度是，前面所有最长递增子序列的长度，加当前数后的长度，的最大值
f[i] = max(f[j] + 1, f[i])

int lengthOfLIS(vector<int>& nums) {
    int n = nums.size();
    vector<int> f(n, 1);  //初始值为1，因为最长递增子序列长度最小为1
    //当前最长递增子序列的长度是，前面所有最长递增子序列的长度，加当前数后的长度，的最大值
    for(int i = 1; i < n; i++){
       for(int j = 0; j < i; j++){
           if(nums[i] > nums[j])
               f[i] = max(f[j] + 1, f[i]);
       }
    }
    int maxs = 1;
    for(int i = 0; i < n; i++)
        maxs = max(f[i], maxs);
    return maxs;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

最后一步遍历整个数组求最大值的时候可以简化，将其写在上面两层循环里面。

int lengthOfLIS(vector<int>& nums) {
    int n = nums.size();
    vector<int> f(n, 1);  //初始值为1，因为最长递增子序列长度最小为1
    int maxs = 1;
    //当前最长递增子序列的长度是，前面所有最长递增子序列的长度，加当前数后的长度，的最大值
    for(int i = 1; i < n; i++){
        for(int j = 0; j < i; j++){
            if(nums[i] > nums[j])
                f[i] = max(f[j] + 1, f[i]);
        }
        maxs = max(f[i], maxs);
    }
    return maxs;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14

对比如下：

7. 编辑距离

思路：

int minDistance(string word1, string word2) {
    int n = word1.size(), m = word2.size();
    vector<vector<int>> f(n+1, vector<int>(m+1));  //注意f从下标1开始取
    //初始化
    for(int i = 0; i <= n; i++)  f[i][0] = i;
    for(int j = 0; j <= m; j++)  f[0][j] = j;
    //遍历
    for(int i = 1; i <= n; i++){
        for(int j = 1; j <= m; j++){
            f[i][j] = min(f[i][j-1] + 1, f[i-1][j] + 1);
            f[i][j] = min(f[i][j], f[i-1][j-1] + (word1[i-1] != word2[j-1]));
        }
    }
    return f[n][m];
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

8. 矩阵区域和

状态表示：sum [ i ] [ j ] = 从第1行第1列到第 i 行第 j 列的矩阵和
状态计算：sum[i][j] = sum[i-1][j] + sum[i][j-1] - sum[i-1][j-1] + mat[i-1][j-1];

//法1：暴力求解
vector<vector<int>> matrixBlockSum(vector<vector<int>>& mat, int k) {
    vector<vector<int>> ans1 = {};
    int m = mat.size();
    if(m == 0)
        return ans1;
    int n = mat[0].size();
    vector<vector<int>> ans(m, vector<int>(n));
    for(int i = 0; i < m; i++){
        for(int j = 0; j < n; j++){
            for(int r = max(0, i-k); r < min(m, i+k+1); r++){
                for(int c = max(0, j-k); c < min(n, j+k+1); c++){
                    ans[i][j] += mat[r][c];
                }
            }
        }
    }
    return ans;
}
//法2：动态规划
vector<vector<int>> matrixBlockSum1(vector<vector<int>>& mat, int k) {
    int m = mat.size();
    int n = mat[0].size();
    vector<vector<int>> ans(m, vector<int>(n));
    vector<vector<int>> sum(m+1, vector<int>(n+1));
    for(int i = 1; i <= m; i++){
        for(int j = 1; j <= n; j++){
            sum[i][j] = sum[i-1][j] + sum[i][j-1] - sum[i-1][j-1] + mat[i-1][j-1];
        }
    }
    for(int i = 0; i < m; i++){
        for(int j = 0; j < n; j++){
        	//限制边界范围：左上角，右下角
            int r1 = max(0, i-k), c1 = max(0, j-k);
            int r2 = min(m-1, i+k), c2 = min(n-1, j+k);  //注意这里是m-1和n-1
            ans[i][j] = sum[r2+1][c2+1] - sum[r2+1][c1] - sum[r1][c2+1] + sum[r1][c1];  //这里的+1也要注意
        }
    }
    return ans;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40

9. 买卖股票最佳时机1（只能一次买卖）

法1：暴力穷举
两层for循环，分别枚举买入和卖出时刻。

//暴力穷举
int maxProfit(vector<int>& prices) {
    int start, end;
    int profit = 0;
    int max;
    for (start = 0; start < prices.size(); start++)
    {
        max = 0;
        for (end = start+1; end < prices.size(); end++)
        {
            if (prices[end] > max)
                max = prices[end];
        }
        if(profit < max - prices[start])
            profit = max - prices[start];
    }
    return profit;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

法2：遍历一次，找当前最小值和最大利润

int maxProfit1(vector<int>& prices) {
    int min_price = prices[0];
    int max_profit = 0;
    int i;
    //遍历一次，找当前最小值和当前最大利润
    for(i = 1; i < prices.size(); i++){
        if(prices[i] < min_price)
            min_price = prices[i];
        else if(prices[i] - min_price > max_profit)
            max_profit = prices[i] - min_price;
    }
    return max_profit;
}
1
2
3
4
5
6
7
8
9
10
11
12
13

法3：通用动态规划
状态表示：
f[i][0]：持有股票最大金
f[i][1]：不持有股票最大金
状态计算：
f[i][0] = max(f[i-1][0], -prices[i]) 保持第i-1天的状态，第i天买入。
f[i][1] = max(f[i-1][1], f[i-1][0] + prices[i]) 保持第i-1天的状态，第i天卖出。

int maxProfit2(vector<int>& prices){
    int n = prices.size();
    vector<vector<int>>f(n, vector<int>(2));
    for(int i = 0; i < n; i++){
        f[i][0] = -prices[0];
        f[i][1] = 0;
    }
    for(int i = 1; i < n; i++){
        f[i][0] = max(f[i-1][0], -prices[i]);
        f[i][1] = max(f[i-1][1], f[i-1][0] + prices[i]);
    }
    return f[n-1][1];
}
1
2
3
4
5
6
7
8
9
10
11
12
13

法4：上述方法的简化
由于当前状态的计算只看上一个状态即可，所以可以用两个变量代替上述二维数组。

int maxProfit3(vector<int>& prices){
    int n = prices.size();
    int hold = -prices[0], unhold = 0;

    for(int i = 1; i < n; i++){
        hold = max(hold, -prices[i]);
        unhold = max(unhold, hold + prices[i]);
    }
    return unhold;
}
1
2
3
4
5
6
7
8
9
10

10. 买卖股票最佳时机2（可多次买卖）

法1：通用动态规划

int maxProfit2(vector<int>& prices){
    int n = prices.size();
    vector<vector<int>>f(n, vector<int>(2));
    for(int i = 0; i < n; i++){
        f[i][0] = -prices[0];
        f[i][1] = 0;
    }
    for(int i = 1; i < n; i++){
        f[i][0] = max(f[i-1][0], f[i-1][1]-prices[i]);
        f[i][1] = max(f[i-1][1], f[i-1][0] + prices[i]);
    }
    return f[n-1][1];
}
1
2
3
4
5
6
7
8
9
10
11
12
13

法2：上述方法化简2

int maxProfit3(vector<int>& prices){
    int n = prices.size();
    int hold = -prices[0], unhold = 0;

    for(int i = 1; i < n; i++){
        hold = max(hold, unhold-prices[i]);
        unhold = max(unhold, hold + prices[i]);
    }
    return unhold;
}
1
2
3
4
5
6
7
8
9
10

对比图如下：

法3：贪心算法

int maxProfit(vector<int>& prices) {
    int i, sum = 0;
    for(i = 0; i < prices.size()-1; i++){
        if(prices[i+1] - prices[i] > 0){
            sum = sum + prices[i+1] - prices[i];
        }
    }
    return sum;
}
1
2
3
4
5
6
7
8
9

11. 背包问题

01背包：有n种物品，每种物品只有一个
完全背包：有n种物品，每种物品有无限个
多重背包：有n种物品，每种物品的个数各不相同

（一）01背包问题

int zeroOne_bag_problem(vector<int> weight, vector<int> value, int bagweight){
    int n = weight.size();
    vector<vector<int>> dp(n, vector<int>(bagweight+1, 0));
    for(int j = weight[0]; j < bagweight+1; j++)
        dp[0][j] = value[0];

    for(int i = 1; i < n; i++){
        for(int j = 1; j < bagweight+1; j++){
            if(j-weight[i] < 0)  dp[i][j] = dp[i-1][j];
            else  dp[i][j] = max(dp[i-1][j], dp[i-1][j-weight[i]] + value[i]);
        }
    }
    return dp[n-1][bagweight];
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14

优化：滚动数组（一维数组）

int zeroOne_bag_problem_1d(vector<int> weight, vector<int> value, int bagweight){
    int n = weight.size();
    vector<int> dp(bagweight + 1);

//    for(int i = 0; i < n; i++){
//        for(int j = bagweight; j > 0; j--){
//            if(j - weight[i] >= 0)
//                dp[j] = max(dp[j], dp[j-weight[i]] + value[i]);
//        }
//    }
//  可以简写为：
    for(int i = 0; i < n; i++)
        for(int j = bagweight; j >= weight[i]; j--)
                dp[j] = max(dp[j], dp[j-weight[i]] + value[i]);
    return dp[bagweight];
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

1. 分割等和子集

思路：
判断能否将数组分割成两个和相等的子集。将整个数组求和，除以2，设为target。找到一个和为target的集合即可。
背包的容量为j，商品价值 = 商品重量，dp[ j ]：背包容量为 j 时所装物品的最大价值。
dp[ j ] = max( dp[ j ], dp[ j - nums[ i ] ] + nums[ i ] )
dp数组初始化为0

bool canPartition(vector<int>& nums) {
    int sum = 0;
    for(auto u: nums)
        sum += u;
    if(sum % 2 == 1)
        return false;

    int n = nums.size();
    int target = sum / 2;
    vector<int> dp(target + 1);
    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]);
        }
    }
    if(dp[target] == target)
        return true;
    return false;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

2. 最后一块石头的重量

思路：
将所有石头分成两堆，使这两堆的重量差最小。=》转化为上一题

int lastStoneWeightII(vector<int>& stones){
    int sum = 0;
    for(int i = 0; i < stones.size(); i++)
        sum += stones[i];
    int target = sum / 2;
    vector<int> dp(target + 1);
    for(int i = 0; i < stones.size(); 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];
}
1
2
3
4
5
6
7
8
9
10
11
12
13

3. 目标和

思路：
将数组分成两堆，一堆为正，一堆为负，两堆之差为t。
背包容量为t，找装满背包的方案数。
本题注意：
dp数组的含义：装满容量为j的背包有dp[j]种方法
递推公式、初始化

int findTargetSumWays(vector<int>& nums, int target) {
    int sum = 0;
    for(auto u: nums)
        sum += u;
    //注意：无方案情况
    if(abs(target) > sum)   return 0;
    sum += target;
    if(sum % 2 == 1)    return 0;

    int t = sum / 2;
    int n = nums.size();
    //装满容量为j的背包有dp[j]种方法
    vector<int> dp(t + 1);
    dp[0] = 1;  //注意：将dp[0]初始化为1
    for(int i = 0; i < n; i++){
        for(int j = t; j >= nums[i]; j--){
            //注意：递推公式与传统背包问题不同，可以想象成常规动态规划。取num[i]不影响方法个数，所以无需+1。
            //如果取nums[i]的话，有dp[j - nums[i]]种取法，将其求和即为总方法数。
            dp[j] += dp[j - nums[i]];  
        }
    }
    return dp[t];
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

4. 一和零

思路：
物体大小：j1个0，j2个1
物体价值：1
背包容量：m个0，n个1
求装满背包的最大价值
dp[j1][j2]：背包容量为j1个0，j2个1时，装满背包的最大价值
dp[j1][j2] = max(dp[j1][j2], dp[j1 - num0][j2 - num1] + 1)

int findMaxForm(vector<string>& strs, int m, int n) {
    vector<vector<int>> dp(m+1, vector<int>(n+1));

    int j1, j2;
    for(int i = 0; i < strs.size(); i++){
        int num0 = count(strs[i].begin(), strs[i].end(), '0');
        int num1 = count(strs[i].begin(), strs[i].end(), '1');

        for(j1 = m; j1 >= num0; j1--){
            for(j2 = n; j2 >= num1; j2--){
                dp[j1][j2] = max(dp[j1][j2], dp[j1 - num0][j2 - num1] + 1);
            }
        }
    }
    return dp[m][n];
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

（二）完全背包问题

int complete_bag_problem_1d(vector<int> weight, vector<int> value, int bagweight){
    int n = weight.size();
    vector<int> dp(bagweight + 1);

    for(int i = 0; i < n; i++)
        //将01背包问题中的从大到小遍历改为从小到大遍历即可
        for(int j = weight[i]; j <=bagweight; j++)
            dp[j] = max(dp[j], dp[j-weight[i]] + value[i]);
    return dp[bagweight];
}
1
2
3
4
5
6
7
8
9
10

1. 零钱兑换2

思想：
背包容量：amount = 5，物品重量：coins = [1, 2, 5]
dp [ j ]：背包容量为 j 时有多少种方法可以装满
组合问题：先遍历物品后遍历背包

int change(int amount, vector<int>& coins) {
    int n = coins.size();
    vector<int> dp(amount + 1);
    dp[0] = 1;  //注意这里需要初始化为1
    for(int i = 0; i < n; i++){
        for(int j = coins[i]; j <= amount; j++){
            dp[j] = dp[j] + dp[j-coins[i]];  //累加：不装i已经满了 + 装i刚好装满了
        }
    }
    return dp[amount];
}
1
2
3
4
5
6
7
8
9
10
11

2. 组合总和4

与上题类似
排列问题：先遍历背包后遍历物品

int combinationSum4(vector<int>& nums, int target) {
    int n = nums.size();
    vector<int> dp(target + 1);
    dp[0] = 1;  //注意这里需要初始化为1
    for(int j = 0; j <= target; j++){
        for(int i = 0; i < n; i++){
        	//注意加限定条件：C++测试⽤例有两个数相加超过int的数据
        	//且不能写成：dp[j] + dp[j-nums[i]] < INT_MAX 的形式，因为相加如果大于INT_MAX就已经报错了，判断没有意义了。
            if(j-nums[i] >= 0 && dp[j] < INT_MAX - dp[j-nums[i]])  
                dp[j] =  dp[j] + dp[j-nums[i]];  //累加：不装i已经满了 + 装i刚好装满了 
        }
    }
    return dp[target];
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14

3. 爬楼梯

简单动态规划：
f [ i ]：爬到第 i 个楼梯的方法数
f [ i ] = f [ i - 1 ] + f [ i - 2 ]

int climbStairs(int n) {
    if(n == 1)
        return 1;
    vector<int> f(n+1);
    f[1] = 1, f[2] = 2;
    for(int i = 3; i < n+1; i++){
        f[i] = f[i-1] + f[i-2];
    }
    return f[n];
}
1
2
3
4
5
6
7
8
9
10

进阶：一次可以爬1个楼梯、2个楼梯……n个楼梯 =》完全背包的排列问题
背包容积：n
物品重量：[1, 2, 3, …, n]
dp[ j ]：背包容积为j时，装满背包的方法数。
其中[1, 2, 2]与[2, 2, 1]为不同的爬楼梯方法，所以为排列数。

4. 零钱兑换

思路：
背包容量：amount=11
物品重量：coins = [1, 2, 5]，物品价值：1
dp [ j ]：装满容量为 j 的背包的最少价值

int coinChange(vector<int>& coins, int amount) {
    int n = coins.size();
    vector<int> dp(amount + 1, INT_MAX);  //由于求min，所以初始化为INT_MAX
    dp[0] = 0;
    for(int i = 0; i < n; i++){
        for(int j = coins[i]; j <= amount; j++){
            if(dp[j-coins[i]] != INT_MAX) // 如果dp[j - coins[i]]是初始值则跳过，说明装满容量为j-coins[i]的背包没有方案
                dp[j] = min(dp[j], dp[j-coins[i]] + 1);
        }
    }
    if(dp[amount] == INT_MAX)  //如果dp[amount]为初始值，则表示没有找到组合
        return -1;
    return dp[amount];
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14

5. 完全平方数

思路：
背包容积：n
物品重量：1^2 , 2^2, 3^2 …
物品价值：1
求装满背包的总价值最少是多少？

int numSquares(int n) {
    vector<int> dp(n+1, INT_MAX);
    dp[0] = 0;
    for(int i = 1; i <= sqrt(n); i++){
        for(int j = pow(i,2); j <= n; j++){
            if(dp[j-pow(i,2)] < INT_MAX -1)
                dp[j] = min(dp[j], dp[j-pow(i,2)] + 1);
        }
    }
    return dp[n];
}
1
2
3
4
5
6
7
8
9
10
11

6. 单词拆分

思路：

bool wordBreak(string s, vector<string>& wordDict){
    // unordered_set提供了一种存储唯一元素的容器
    // unordered_set 内部使用哈希表来存储元素，这使得其在平均情况下对元素的插入、删除和查找操作都有常数时间复杂度（O(1)）。
    // 然而，在最坏的情况下，这些操作的时间复杂度可能会退化到线性时间（O(n)），例如当哈希函数产生了很多冲突时。
    // 这里，使用unordered_set的原因是：查找方便
    unordered_set<string> wordSet(wordDict.begin(), wordDict.end());
    vector<bool> dp(s.size()+1, false);
    dp[0] = true;
    for(int i = 1; i <= s.size(); i++){
        for(int j = 0; j < i; j++){
            string word = s.substr(j, i-j);  //截取字符串s中j到i的部分，j为起始位置，i-j为长度。
            if(dp[j] == true && wordSet.find(word) != wordSet.end())  //wordSet.find(word) != wordSet.end()表示在wordSet中找到了word
                dp[i] = true;
        }
    }
    return dp[s.size()];
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17