动态规划

1、斐波那契数列

1.1、问题描述

大家都知道斐波那契数列，现在要求输入一个正整数 n ，请你输出斐波那契数列的第 n 项。

示例1
输入：4
返回值：3
说明：
根据斐波那契数列的定义可知，fib(1)=1,fib(2)=1,fib(3)=fib(3-1)+fib(3-2)=2,fib(4)=fib(4-1)+fib(4-2)=3，所以答案为3。
示例2
输入：1
返回值：1
示例3
输入：2
返回值：1

1.2、思路及代码

1.2.1、递归

思路：

如果n小于等于0，返回0；如果n等于1，返回1。
否则，递归计算第n项，即第n-1项和第n-2项的和。

缺点：递归方法的效率较低，因为会重复计算很多项。

参考代码：

C++

#include <iostream>

int fibonacci_recursive(int n) {
    if (n <= 0) {
        return 0;
    } else if (n == 1) {
        return 1;
    } else {
        // 递归计算第n项
        return fibonacci_recursive(n - 1) + fibonacci_recursive(n - 2);
    }
}

int main() {
    int n = 10;  // 你可以将n替换为任意正整数
    int result = fibonacci_recursive(n);
    
    std::cout << "斐波那契数列第" << n << "项是：" << result << std::endl;
    
    return 0;
}

1.2.2、动态规划

思路：

如果n小于等于0，返回0；如果n等于1，返回1。
使用一个数组dp保存中间结果，初始化前两项。
从第3项开始，依次计算每一项的值，直到第n项。

参考代码：

C++

#include <iostream>
#include <vector>

int fibonacci_dynamic(int n) {
    if (n <= 0) {
        return 0;
    } else if (n == 1) {
        return 1;
    } else {
        std::vector<int> dp(n + 1, 0);  // 使用动态规划数组保存中间结果
        dp[1] = 1;  // 初始化第1项和第2项
        for (int i = 2; i <= n; ++i) {
            dp[i] = dp[i - 1] + dp[i - 2];  // 计算第i项
        }
        return dp[n];
    }
}

int main() {
    int n = 10;  // 你可以将n替换为任意正整数
    int result = fibonacci_dynamic(n);
    
    std::cout << "斐波那契数列第" << n << "项是：" << result << std::endl;
    
    return 0;
}

2、跳台阶

2.1、问题描述

一只青蛙一次可以跳上1级台阶，也可以跳上2级。求该青蛙跳上一个 n 级的台阶总共有多少种跳法（先后次序不同算不同的结果）。

示例1
输入：2
返回值：2
说明：青蛙要跳上两级台阶有两种跳法，分别是：先跳一级，再跳一级或者直接跳两级。因此答案为2
示例2
输入：7
返回值：21

2.2、思路及代码

2.2.1、递归

思路：

如果n小于等于0，返回0；
如果n等于1，只有一级台阶，只有一种跳法；
如果n等于2，有两级台阶，可以选择一次跳1级或者直接跳2级，共两种跳法；
对于n大于等于3的情况，递归公式为f(n) = f(n-1) + f(n-2)，即第n级的跳法等于前两级的跳法之和。

参考代码：

C++

#include <iostream>

int jumpWaysRecursive(int n) {
    if (n <= 0) {
        return 0;
    } else if (n == 1) {
        return 1;
    } else if (n == 2) {
        return 2;
    } else {
        // 递归公式：f(n) = f(n-1) + f(n-2)
        return jumpWaysRecursive(n - 1) + jumpWaysRecursive(n - 2);
    }
}

int main() {
    int n = 5;  // 你可以将n替换为任意正整数
    int ways = jumpWaysRecursive(n);
    
    std::cout << "青蛙跳上" << n << "级台阶共有 " << ways << " 种跳法。" << std::endl;
    
    return 0;
}

2.2.2、动态规划

思路：

如果n小于等于0，返回0；
如果n等于1，只有一级台阶，只有一种跳法；
如果n等于2，有两级台阶，可以选择一次跳1级或者直接跳2级，共两种跳法；
对于n大于等于3的情况，使用动态规划数组dp保存中间结果，从第3级开始计算每一级的跳法，等于前两级的跳法之和。

参考代码：

C++

#include <iostream>
#include <vector>

int jumpWays(int n) {
    if (n <= 0) {
        return 0;
    } else if (n == 1) {
        return 1;  // 只有一级台阶，只有一种跳法
    } else if (n == 2) {
        return 2;  // 有两级台阶，可以选择一次跳1级或者直接跳2级，共两种跳法
    } else {
        std::vector<int> dp(n + 1, 0);  // 使用动态规划数组保存中间结果
        dp[1] = 1;  // 初始化第1级和第2级的跳法
        dp[2] = 2;
        for (int i = 3; i <= n; ++i) {
            // 计算第i级台阶的跳法，等于前两级的跳法之和
            dp[i] = dp[i - 1] + dp[i - 2];
        }
        return dp[n];
    }
}

int main() {
    int n = 5;  // 你可以将n替换为任意正整数
    int ways = jumpWays(n);
    
    std::cout << "青蛙跳上" << n << "级台阶共有 " << ways << " 种跳法。" << std::endl;
    
    return 0;
}

3、最小花费爬楼梯

3.1、问题描述

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

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

示例1
输入：[2,5,20]
返回值：5
说明：你将从下标为1的台阶开始，支付5 ，向上爬两个台阶，到达楼梯顶部。总花费为5
示例2
输入：[1,100,1,1,1,90,1,1,80,1]
返回值：6
说明：
你将从下标为 0 的台阶开始。 1.支付 1 ，向上爬两个台阶，到达下标为 2 的台阶。 2.支付 1 ，向上爬两个台阶，到达下标为 4 的台阶。 3.支付 1 ，向上爬两个台阶，到达下标为 6 的台阶。 4.支付 1 ，向上爬一个台阶，到达下标为 7 的台阶。 5.支付 1 ，向上爬两个台阶，到达下标为 9 的台阶。 6.支付 1 ，向上爬一个台阶，到达楼梯顶部。总花费为 6 。

3.2、思路及代码

3.2.1、递归

思路：

定义递归函数 minCostRecursive，表示从当前台阶开始爬楼梯到顶部的最低花费。
对于当前台阶 i，有两种选择：
1. 选择从第 i 个台阶开始爬，花费为 cost[i]，然后递归计算从第 i+1 个台阶到顶部的最低花费。
2. 选择从第 i+1 个台阶开始爬，花费为 cost[i+1]，然后递归计算从第 i+2 个台阶到顶部的最低花费。
递归终止条件是到达楼梯顶部，即 i 超过数组 cost 的长度，此时花费为0。

参考代码：

C++

#include <iostream>
#include <vector>
#include <algorithm>

// 递归方法
int minCostRecursive(const std::vector<int>& cost, int i) {
    if (i >= cost.size()) {
        return 0;
    }

    // 选择从第 i 个台阶开始爬，或者从第 i+1 个台阶开始爬
    return cost[i] + std::min(minCostRecursive(cost, i + 1), minCostRecursive(cost, i + 2));
}

int main() {
    std::vector<int> cost = {10, 15, 20};

    int recursiveResult = minCostRecursive(cost, 0);
    std::cout << "递归方法最低花费: " << recursiveResult << std::endl;
}

3.2.2、动态规划

思路：

定义一个动态规划数组 dp，其中 dp[i] 表示从第 i 个台阶到顶部的最低花费。
从顶部开始向底部计算，因为我们要计算每个位置的最低花费。
递推关系：dp[i] = cost[i] + min(dp[i+1], dp[i+2])。即当前位置的最低花费等于当前位置的花费加上下一步和下两步的最低花费中的较小者。
最终，dp[0] 即为从底部到顶部的最低花费。

参考代码：

C++

#include <iostream>
#include <vector>
#include <algorithm>

// 动态规划方法
int minCostDP(const std::vector<int>& cost) {
    int n = cost.size();
    std::vector<int> dp(n + 1, 0);

    for (int i = n - 1; i >= 0; i--) {
        dp[i] = cost[i] + std::min(dp[i + 1], dp[i + 2]);
    }

    return dp[0];
}

int main() {
    std::vector<int> cost = {10, 15, 20};

    int dpResult = minCostDP(cost);
    std::cout << "动态规划方法最低花费: " << dpResult << std::endl;

    return 0;
}

4、最长公共子序列(二)

4.1、问题描述

给定两个字符串str1和str2，输出两个字符串的最长公共子序列。如果最长公共子序列为空，则返回"-1"。目前给出的数据，仅仅会存在一个最长的公共子序列。

示例1
输入："1A2C3D4B56","B1D23A456A"
返回值："123456"
示例2
输入："abc","def"
返回值："-1"
示例3
输入："abc","abc"
返回值："abc"
示例4
输入："ab",""
返回值："-1"

4.2、思路及代码

思路：

定义动态规划数组 dp，其中 dp[i][j] 表示 str1[0...i-1] 和 str2[0...j-1] 的最长公共子序列的长度。
初始化第一行和第一列，即 dp[i][0] 和 dp[0][j]，表示一个字符串和空串的最长公共子序列，都为0。
递推关系：
1. 如果 str1[i-1] == str2[j-1]，说明当前字符相同，可以将这个字符加入最长公共子序列，即 dp[i][j] = dp[i-1][j-1] + 1。
2. 如果 str1[i-1] != str2[j-1]，说明当前字符不同，那么最长公共子序列的长度取决于去掉一个字符后的子问题，即 dp[i][j] = max(dp[i-1][j], dp[i][j-1])。
最终，dp[m][n] 即为 str1 和 str2 的最长公共子序列的长度。

参考代码：

C++

#include <iostream>
#include <vector>
#include <string>

std::string longestCommonSubsequence(const std::string& str1, const std::string& str2) {
    int m = str1.size();
    int n = str2.size();

    // 初始化动态规划数组
    std::vector<std::vector<int>> dp(m + 1, std::vector<int>(n + 1, 0));

    // 计算最长公共子序列的长度
    for (int i = 1; i <= m; i++) {
        for (int j = 1; j <= n; j++) {
            if (str1[i - 1] == str2[j - 1]) {
                dp[i][j] = dp[i - 1][j - 1] + 1;
            } else {
                dp[i][j] = std::max(dp[i - 1][j], dp[i][j - 1]);
            }
        }
    }

    // 构造最长公共子序列
    int len = dp[m][n];
    if (len == 0) {
        return "-1"; // 没有最长公共子序列，返回"-1"
    }

    std::string result(len, ' '); // 用于存储最长公共子序列
    int i = m, j = n;
    while (i > 0 && j > 0) {
        if (str1[i - 1] == str2[j - 1]) {
            result[--len] = str1[i - 1];
            i--;
            j--;
        } else if (dp[i - 1][j] > dp[i][j - 1]) {
            i--;
        } else {
            j--;
        }
    }

    return result;
}

int main() {
    std::string str1 = "ABCD";
    std::string str2 = "ACDF";

    std::string result = longestCommonSubsequence(str1, str2);

    std::cout << "最长公共子序列: " << result << std::endl;

    return 0;
}

5、最长公共子串

5.1、问题描述

给定两个字符串str1和str2,输出两个字符串的最长公共子串。题目保证str1和str2的最长公共子串存在且唯一。

示例1
输入："1AB2345CD","12345EF"
返回值："2345"

5.2、思路及代码

思路：

定义动态规划数组 dp，其中 dp[i][j] 表示以 str1[i-1] 和 str2[j-1] 为结尾的最长公共子串的长度。
初始化第一行和第一列，即 dp[i][0] 和 dp[0][j]，表示一个字符串和空串的最长公共子串，都为0。
递推关系：
1. 如果 str1[i-1] == str2[j-1]，说明当前字符相同，可以将这个字符加入最长公共子串，即 dp[i][j] = dp[i-1][j-1] + 1。
2. 如果 str1[i-1] != str2[j-1]，说明当前字符不同，最长公共子串的长度直接为0，即 dp[i][j] = 0。
在递推过程中，记录最长公共子串的长度和结束位置。
最终，最长公共子串的长度即为记录的最大长度，根据结束位置截取子串。

参考代码：

C++

#include <iostream>
#include <vector>
#include <string>

std::string longestCommonSubstring(const std::string& str1, const std::string& str2) {
    int m = str1.size();
    int n = str2.size();

    // 初始化动态规划数组
    std::vector<std::vector<int>> dp(m + 1, std::vector<int>(n + 1, 0));

    int maxLen = 0; // 记录最长公共子串的长度
    int endIndex = 0; // 记录最长公共子串的结束位置

    // 计算最长公共子串的长度
    for (int i = 1; i <= m; i++) {
        for (int j = 1; j <= n; j++) {
            if (str1[i - 1] == str2[j - 1]) {
                dp[i][j] = dp[i - 1][j - 1] + 1;

                // 更新最长公共子串信息
                if (dp[i][j] > maxLen) {
                    maxLen = dp[i][j];
                    endIndex = i - 1; // 记录最长公共子串的结束位置
                }
            } else {
                dp[i][j] = 0;
            }
        }
    }

    // 根据最长公共子串的结束位置截取子串
    std::string result = str1.substr(endIndex - maxLen + 1, maxLen);

    return result;
}

int main() {
    std::string str1 = "ABCABC";
    std::string str2 = "BCABCD";

    std::string result = longestCommonSubstring(str1, str2);

    std::cout << "最长公共子串: " << result << std::endl;

    return 0;
}

6、不同路径的数目(一)

6.1、问题描述

一个机器人在m×n大小的地图的左上角（起点）。

机器人每次可以向下或向右移动。机器人要到达地图的右下角（终点）。

可以有多少种不同的路径从起点走到终点？

备注：m和n小于等于100,并保证计算结果在int范围内

示例1
输入：2,1
返回值：1
示例2
输入：2,2
返回值：2

6.2、思路及代码

思路：

定义一个二维动态规划数组 dp，其中 dp[i][j] 表示从起点到达位置 (i, j) 的不同路径数。
初始化边界条件，即第一行和第一列的路径数都为1，因为机器人只能向右或向下移动。
递推关系：dp[i][j] = dp[i-1][j] + dp[i][j-1]，表示当前位置的路径数等于上面位置和左边位置的路径数之和。
根据递推关系，从左上角开始逐步计算到右下角的路径数。
最终，右下角的值 dp[m-1][n-1] 即为起点到终点的不同路径数。

参考代码：

C++

#include <iostream>
#include <vector>

int uniquePaths(int m, int n) {
    // 定义二维动态规划数组，初始化为0
    std::vector<std::vector<int>> dp(m, std::vector<int>(n, 0));

    // 初始化边界条件
    for (int i = 0; i < m; i++) {
        dp[i][0] = 1; // 第一列的路径数都为1
    }

    for (int j = 0; j < n; j++) {
        dp[0][j] = 1; // 第一行的路径数都为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]; // 返回右下角的路径数
}

int main() {
    int m = 3;
    int n = 7;

    int result = uniquePaths(m, n);

    std::cout << "不同路径数：" << result << std::endl;

    return 0;
}

7、矩阵的最小路径和

7.1、问题描述

给定一个 n * m 的矩阵 a，从左上角开始每次只能向右或者向下走，最后到达右下角的位置，路径上所有的数字累加起来就是路径和，输出所有的路径中最小的路径和。

例如：当输入[[1,3,5,9],[8,1,3,4],[5,0,6,1],[8,8,4,0]]时，对应的返回值为12，
所选择的最小累加和路径如下图所示：
示例1
输入：[[1,3,5,9],[8,1,3,4],[5,0,6,1],[8,8,4,0]]
返回值：12
示例2
输入：[[1,2,3],[1,2,3]]
返回值：7

7.2、思路及代码

思路：

定义一个二维动态规划数组 dp，其中 dp[i][j] 表示从左上角到达位置 (i, j) 的最小路径和。
初始化边界条件，即第一行和第一列的路径和，因为只能向右或向下移动，所以第一行和第一列的路径和累加即可。
递推关系：dp[i][j] = a[i][j] + min(dp[i-1][j], dp[i][j-1])，表示当前位置的最小路径和等于当前位置的值加上上面和左边最小路径和的较小值。
根据递推关系，从左上角开始逐步计算到右下角的最小路径和。
最终，右下角的值 dp[n-1][m-1] 即为最小路径和。

参考代码：

C++

#include <iostream>
#include <vector>

int minPathSum(std::vector<std::vector<int>>& a) {
    int n = a.size();
    int m = a[0].size();

    // 定义二维动态规划数组，初始化为0
    std::vector<std::vector<int>> dp(n, std::vector<int>(m, 0));

    // 初始化边界条件
    dp[0][0] = a[0][0];

    for (int i = 1; i < n; i++) {
        dp[i][0] = dp[i - 1][0] + a[i][0]; // 第一列的最小路径和
    }

    for (int j = 1; j < m; j++) {
        dp[0][j] = dp[0][j - 1] + a[0][j]; // 第一行的最小路径和
    }

    // 递推计算最小路径和
    for (int i = 1; i < n; i++) {
        for (int j = 1; j < m; j++) {
            dp[i][j] = a[i][j] + std::min(dp[i - 1][j], dp[i][j - 1]);
        }
    }

    return dp[n - 1][m - 1]; // 返回右下角的最小路径和
}

int main() {
    std::vector<std::vector<int>> matrix = {{1, 3, 1},
                                           {1, 5, 1},
                                           {4, 2, 1}};

    int result = minPathSum(matrix);

    std::cout << "最小路径和：" << result << std::endl;

    return 0;
}

8、把数字翻译成字符串

8.1、问题描述

有一种将字母编码成数字的方式：'a'->1, 'b->2', ... , 'z->26'。

现在给一串数字，返回有多少种可能的译码结果。

示例1
输入："12"
返回值：2
说明：2种可能的译码结果（”ab” 或”l”）
示例2
输入："31717126241541717"
返回值：192
说明：192种可能的译码结果

8.2、思路及代码

思路：

定义一个一维数组 dp，其中 dp[i] 表示字符串的前 i 个字符（包括第 i 个字符）的译码方式数量。
初始化边界条件，即空字符串和第一个字符的译码方式数量。
递推关系：
1. 如果当前字符不为 '0'，则可以将其作为单独的一个字母进行译码，此时 dp[i] += dp[i-1]。
2. 如果当前字符和前一个字符组成的数字在 10 到 26 之间，可以将其作为一个字母进行译码，此时 dp[i] += dp[i-2]。
最终，dp[n] 即为字符串的译码方式数量。

参考代码：

C++

#include <iostream>
#include <string>
#include <vector>

int numDecodings(std::string s) {
    int n = s.size();
    
    // 边界条件
    if (n == 0 || s[0] == '0') {
        return 0;
    }

    // 定义动态规划数组
    std::vector<int> dp(n + 1, 0);
    
    // 初始化边界条件
    dp[0] = 1;
    dp[1] = 1;

    // 递推计算译码方式数量
    for (int i = 2; i <= n; i++) {
        if (s[i - 1] != '0') {
            dp[i] += dp[i - 1];
        }

        int twoDigit = std::stoi(s.substr(i - 2, 2));
        if (twoDigit >= 10 && twoDigit <= 26) {
            dp[i] += dp[i - 2];
        }
    }

    return dp[n];
}

int main() {
    std::string code = "226";
    
    int result = numDecodings(code);

    std::cout << "译码方式数量：" << result << std::endl;

    return 0;
}

9、兑换零钱(一)

9.1、问题描述

给定数组arr，arr中所有的值都为正整数且不重复。每个值代表一种面值的货币，每种面值的货币可以使用任意张，再给定一个aim，代表要找的钱数，求组成aim的最少货币数。

如果无解，请返回-1。

示例1
输入：[5,2,3],20
返回值：4
示例2
输入：[5,2,3],0
返回值：0
示例3
输入：[3,5],2
返回值：-1

9.2、思路及代码

思路：

定义一个一维数组 dp，其中 dp[i] 表示组成金额 i 所需的最少货币数量。
初始化边界条件，即金额为 0 时，需要的货币数量为 0；对于其他金额，初始化为一个较大的值（这里使用 INT_MAX）。
递推关系：
1. 对于每个面值的货币，遍历金额从 coin 到 aim，更新 dp[j] = min(dp[j], dp[j-coin] + 1)。
最终，dp[aim] 即为组成目标金额所需的最少货币数量。

参考代码：

C++

#include <iostream>
#include <vector>
#include <climits>

int minCoins(std::vector<int>& coins, int aim) {
    int n = coins.size();

    // 定义动态规划数组
    std::vector<int> dp(aim + 1, INT_MAX);

    // 初始化边界条件
    dp[0] = 0;

    // 递推计算最少货币数量
    for (int i = 0; i < n; i++) {
        for (int j = coins[i]; j <= aim; j++) {
            if (dp[j - coins[i]] != INT_MAX) {
                dp[j] = std::min(dp[j], dp[j - coins[i]] + 1);
            }
        }
    }

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

int main() {
    std::vector<int> coins = {1, 2, 5};
    int aim = 11;

    int result = minCoins(coins, aim);

    std::cout << "组成目标金额的最少货币数量：" << result << std::endl;

    return 0;
}

10、最长上升子序列(一)

10.1、问题描述

给定一个长度为 n 的数组 arr，求它的最长严格上升子序列的长度。

所谓子序列，指一个数组删掉一些数（也可以不删）之后，形成的新数组。例如 [1,5,3,7,3] 数组，其子序列有：[1,3,3]、[7] 等。但 [1,6]、[1,3,5] 则不是它的子序列。

我们定义一个序列是严格上升的，当且仅当该序列不存在两个下标 i 和 j 满足i<j 且arri≥arrj。

输入：[6,3,1,5,2,3,7]
返回值：4
说明：该数组最长上升子序列为 [1,2,3,7] ，长度为4

10.2、思路及代码

思路：

定义一个一维数组 dp，其中 dp[i] 表示以第 i 个元素为结尾的最长严格上升子序列的长度。
初始化边界条件，即每个元素单独构成一个子序列，因此初始长度都为 1。
递推关系：
1. 对于每个元素 arr[i]，遍历其前面的元素 arr[j]（j 从 0 到 i-1），如果 arr[i] > arr[j]，更新 dp[i] = max(dp[i], dp[j] + 1)。
最终，结果为所有 dp 中的最大值。

参考代码：

C++

#include <iostream>
#include <vector>

int lengthOfLIS(std::vector<int>& arr) {
    int n = arr.size();
    std::vector<int> dp(n, 1);  // 初始化为每个元素单独构成一个子序列

    // 递推计算最长严格上升子序列的长度
    for (int i = 1; i < n; i++) {
        for (int j = 0; j < i; j++) {
            if (arr[i] > arr[j]) {
                dp[i] = std::max(dp[i], dp[j] + 1);
            }
        }
    }

    // 最终结果为 dp 中的最大值
    int result = 0;
    for (int i = 0; i < n; i++) {
        result = std::max(result, dp[i]);
    }

    return result;
}

int main() {
    std::vector<int> arr = {10, 9, 2, 5, 3, 7, 101, 18};

    int result = lengthOfLIS(arr);

    std::cout << "最长严格上升子序列的长度：" << result << std::endl;

    return 0;
}

11、连续子数组的最大和

11.1、问题描述

输入一个长度为n的整型数组array，数组中的一个或连续多个整数组成一个子数组，子数组最小长度为1。求所有子数组的和的最大值。

示例1
输入：[1,-2,3,10,-4,7,2,-5]
返回值：18
说明：经分析可知，输入数组的子数组[3,10,-4,7,2]可以求得最大和为18
示例2
输入：[2]
返回值：2
示例3
输入：[-10]
返回值：-10

11.2、思路及代码

思路：

维护一个一维数组 dp，其中 dp[i] 表示以第 i 个元素结尾的子数组的和的最大值。
初始化 dp[0] 为数组的第一个元素。
递推关系：
1. 对于每个元素 array[i]，判断其与之前的子数组的关系，如果 dp[i-1] > 0，说明之前的子数组和对当前元素有增益，可以加到当前子数组中，更新 dp[i] = dp[i-1] + array[i]。
2. 如果 dp[i-1] <= 0，说明之前的子数组和对当前元素没有增益，当前元素自成一个子数组，更新 dp[i] = array[i]。
最终，结果为 dp 中的最大值。

参考代码：

C++

#include <iostream>
#include <vector>

// 计算数组中所有子数组和的最大值
int maxSubArraySum(std::vector<int>& array) {
    int n = array.size();
    std::vector<int> dp(n, 0);

    dp[0] = array[0];

    for (int i = 1; i < n; i++) {
        // 判断之前子数组和是否对当前元素有增益
        // 如果有增益，则加到当前子数组中；否则，当前元素自成一个子数组
        dp[i] = std::max(dp[i-1] + array[i], array[i]);
    }

    // 找到 dp 数组中的最大值作为最终结果
    int result = dp[0];
    for (int i = 1; i < n; i++) {
        result = std::max(result, dp[i]);
    }

    return result;
}

int main() {
    std::vector<int> array = {-2, 1, -3, 4, -1, 2, 1, -5, 4};

    int result = maxSubArraySum(array);

    std::cout << "所有子数组的和的最大值：" << result << std::endl;

    return 0;
}

12、最长回文子串

12.1、问题描述

对于长度为n的一个字符串A（仅包含数字，大小写英文字母），请设计一个高效算法，计算其中最长回文子串的长度。

示例1
输入："ababc"
返回值：3
说明：最长的回文子串为"aba"与"bab"，长度都为3
示例2
输入："abbba"
返回值：5
示例3
输入："b"
返回值：1

12.2、思路及代码

思路：

定义状态：使用二维数组 dp，其中 dp[i][j] 表示字符串 A 从第 i 个字符到第 j 个字符是否构成回文子串。
初始化：将所有长度为 1 的子串都初始化为回文子串，即 dp[i][i] = true。
状态转移方程：通过状态转移方程来填充数组。状态转移方程为 dp[i][j] = (A[i] == A[j] && (len == 2 || dp[i + 1][j - 1]))，其中 len 表示当前子串的长度。这表示当前子串是回文的条件是首尾字符相等且去掉首尾之后的子串也是回文。
更新最长回文子串的长度：在状态转移的过程中，不断更新记录最长回文子串的长度。

参考代码：

C++

#include <iostream>
#include <vector>

// 计算最长回文子串的长度
int longestPalindrome(std::string& A) {
    int n = A.size();
    
    // 创建一个二维动态规划数组，dp[i][j] 表示字符串 A 从第 i 个字符到第 j 个字符是否是回文子串
    std::vector<std::vector<bool>> dp(n, std::vector<bool>(n, false));

    // 初始化，单个字符一定是回文子串
    for (int i = 0; i < n; i++) {
        dp[i][i] = true;
    }

    int maxLen = 1; // 记录最长回文子串的长度

    // 从长度为2的子串开始，逐步扩展到整个字符串
    for (int len = 2; len <= n; len++) {
        for (int i = 0; i <= n - len; i++) {
            int j = i + len - 1; // 子串的右边界

            // 当前子串是回文的条件是首尾字符相等且去掉首尾之后的子串也是回文
            dp[i][j] = (A[i] == A[j] && (len == 2 || dp[i + 1][j - 1]));

            if (dp[i][j]) {
                maxLen = std::max(maxLen, len); // 更新最长回文子串的长度
            }
        }
    }

    return maxLen;
}

int main() {
    std::string str = "babad";

    int result = longestPalindrome(str);

    std::cout << "最长回文子串的长度：" << result << std::endl;

    return 0;
}

13、数字字符串转化成IP地址

13.1、问题描述

现在有一个只包含数字的字符串，将该字符串转化成IP地址的形式，返回所有可能的情况。

例如：

给出的字符串为"25525522135",

返回["255.255.22.135", "255.255.221.35"]. (顺序没有关系)

示例1
输入："25525522135"
返回值：["255.255.22.135","255.255.221.35"]
示例2
输入："1111"
返回值：["1.1.1.1"]
示例3
输入："000256"
返回值：[]

13.2、思路及代码

思路：

状态定义：定义一个二维动态规划数组dp，其中dp[i][j]表示字符串从位置0到i的子串能够形成j段有效的IP地址。
状态转移方程：对于每一位数字，我们可以选择将其作为一段IP地址的开始，然后看后面的数字能够形成多少段IP地址。状态转移方程为dp[i][j] += dp[k][j-1]，其中k表示从0到i的某个位置。
初始化：对于第一列（j=0），表示没有IP地址，所以全部初始化为1。
重构IP地址：遍历所有可能的分段，将满足条件的分段组合成IP地址。

参考代码：

C++

#include <iostream>
#include <vector>
#include <string>

using namespace std;

vector<string> restoreIPAddresses(const string& s) {
    vector<string> result; // 存储最终结果的数组

    int n = s.length();

    if (n < 4 || n > 12) {
        return result;  // 输入无效，返回空结果
    }

    // 动态规划数组，dp[i][j]表示字符串从位置0到i的子串能够形成j段有效的IP地址
    vector<vector<int>> dp(n + 1, vector<int>(4, 0));

    // 初始化，对于第一列（j=0），表示没有IP地址，所以全部初始化为1。
    for (int i = 0; i <= n; ++i) {
        dp[i][0] = 1;
    }

    // 动态规划
    for (int j = 1; j <= 3; ++j) {
        for (int i = 1; i <= n; ++i) {
            for (int k = i - 1; k >= 0; --k) {
                if (i - k <= 3 && stoi(s.substr(k, i - k)) <= 255) {
                    dp[i][j] += dp[k][j - 1];
                }
            }
        }
    }

    // 重构IP地址
    for (int i = 1; i <= 3 && i < n; ++i) {
        for (int j = 1; j <= 3 && i + j < n; ++j) {
            for (int k = 1; k <= 3 && i + j + k < n; ++k) {
                int l = n - i - j - k;
                if (l >= 1 && l <= 3 && stoi(s.substr(0, i)) <= 255 && stoi(s.substr(i, j)) <= 255 &&
                    stoi(s.substr(i + j, k)) <= 255 && stoi(s.substr(i + j + k, l)) <= 255) {
                    result.push_back(s.substr(0, i) + "." + s.substr(i, j) + "." + s.substr(i + j, k) + "." +
                                     s.substr(i + j + k, l));
                }
            }
        }
    }

    return result; // 返回所有可能的IP地址
}

int main() {
    string s = "25525511135";
    vector<string> result = restoreIPAddresses(s);

    cout << "所有可能的IP地址：" << endl;
    for (const string& ip : result) {
        cout << ip << endl;
    }

    return 0;
}

14、编辑距离(一)

14.1、问题描述

给定两个字符串 str1 和 str2 ，请你算出将 str1 转为 str2 的最少操作数。

你可以对字符串进行3种操作：

1.插入一个字符

2.删除一个字符

3.修改一个字符。

字符串长度满足1≤n≤1000 ，保证字符串中只出现小写英文字母。

示例1
输入："nowcoder","new"
返回值：6
说明：
"nowcoder"=>"newcoder"(将'o'替换为'e')，修改操作1次 "nowcoder"=>"new"(删除"coder")，删除操作5次
示例2
输入："intention","execution"
返回值：5
说明：
一种方案为: 因为2个长度都是9，后面的4个后缀的长度都为"tion"，于是从"inten"到"execu"逐个修改即可
示例3
输入："now","nowcoder"
返回值：5

14.2、思路及代码

思路：

定义状态：使用二维数组 dp[i][j] 表示将 str1 的前 i 个字符转换为 str2 的前 j 个字符所需的最小操作数。
初始化状态：
1. dp[i][0] 表示将 str1 的前 i 个字符转为空串 "" 的最小操作数，即删除操作数，因此 dp[i][0] = i。
2. dp[0][j] 表示将空串 "" 转为 str2 的前 j 个字符的最小操作数，即插入操作数，因此 dp[0][j] = j。
状态转移方程：
1. 如果 str1[i-1] == str2[j-1]，表示当前字符相同，无需额外操作，dp[i][j] = dp[i-1][j-1]。
2. 如果 str1[i-1] != str2[j-1]，有三种操作方式：
  - 插入操作：dp[i][j] = dp[i][j-1] + 1，即将 str1 的前 i 个字符转为 str2 的前 j-1 个字符，然后插入一个字符。
  - 删除操作：dp[i][j] = dp[i-1][j] + 1，即将 str1 的前 i-1 个字符转为 str2 的前 j 个字符，然后删除一个字符。
  - 替换操作：dp[i][j] = dp[i-1][j-1] + 1，即将 str1 的前 i-1 个字符转为 str2 的前 j-1 个字符，然后替换一个字符。
遍历顺序：
1. 外层循环遍历 i，表示 str1 的前 i 个字符。
2. 内层循环遍历 j，表示 str2 的前 j 个字符。
返回结果：
1. 最终结果存储在 dp[n][m] 中，其中 n 和 m 分别是 str1 和 str2 的长度。

参考代码：

C++

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int minDistance(const string& word1, const string& word2) {
    int n = word1.length();
    int m = word2.length();

    // 初始化动态规划数组
    vector<vector<int>> dp(n + 1, vector<int>(m + 1, 0));

    // 初始化边界状态
    for (int i = 0; i <= n; ++i) {
        dp[i][0] = i;
    }

    for (int j = 0; j <= m; ++j) {
        dp[0][j] = j;
    }

    // 动态规划遍历
    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= m; ++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[n][m];
}

int main() {
    string str1 = "horse";
    string str2 = "ros";

    int result = minDistance(str1, str2);

    cout << "将字符串 " << str1 << " 转为 " << str2 << " 的最小操作数为: " << result << endl;

    return 0;
}

15、正则表达式匹配

15.1、问题描述

请实现一个函数用来匹配包括'.'和'*'的正则表达式。

1.模式中的字符'.'表示任意一个字符

2.模式中的字符'*'表示它前面的字符可以出现任意次（包含0次）。

在本题中，匹配是指字符串的所有字符匹配整个模式。例如，字符串"aaa"与模式"a.a"和"abaca"匹配，但是与"aa.a"和"ab*a"均不匹配。

示例1
输入："aaa","a*a"
返回值：true
说明：中间的*可以出现任意次的a，所以可以出现1次a，能匹配上
示例2
输入："aad","cad"
返回值：true
说明：
因为这里 c 为 0 个，a被重复一次， * 表示零个或多个a。因此可以匹配字符串 "aad"。
示例3
输入："a",".*"
返回值：true
说明："." 表示可匹配零个或多个（''）任意字符（'.'）

15.2、思路及代码

思路：

定义状态：使用二维数组 dp[i][j] 表示字符串 s 的前 i 个字符是否与模式 p 的前 j 个字符匹配。
初始化状态：
1. dp[0][0] 表示空字符串和空模式的匹配，为 true。
2. 对于第一行 dp[0][j]，表示空字符串与模式的匹配，只有当模式中出现 * 时，可以选择将前面的字符匹配0次。
状态转移方程：
1. 如果 p[j-1] 是普通字符或者 .，则 dp[i][j] = dp[i-1][j-1]，表示当前字符匹配成功。
2. 如果 p[j-1] 是 *，则有两种情况：
  - 匹配0次：dp[i][j] = dp[i][j-2]
  - 匹配多次：dp[i][j] = dp[i-1][j] && (s[i-1] == p[j-2] || p[j-2] == '.')
遍历顺序：
1. 外层循环遍历 i，表示字符串 s 的前 i 个字符。
2. 内层循环遍历 j，表示模式 p 的前 j 个字符。
返回结果：
1. 最终结果存储在 dp[m][n] 中，其中 m 和 n 分别是字符串 s 和模式 p 的长度。

参考代码：

C++

#include <iostream>
#include <vector>

using namespace std;

bool isMatch(string s, string p) {
    int m = s.length();
    int n = p.length();

    // 初始化动态规划数组
    vector<vector<bool>> dp(m + 1, vector<bool>(n + 1, false));

    // 空字符串和空模式匹配
    dp[0][0] = true;

    // 处理空字符串与模式的匹配
    for (int j = 1; j <= n; ++j) {
        if (p[j - 1] == '*') {
            dp[0][j] = dp[0][j - 2];
        }
    }

    // 动态规划遍历
    for (int i = 1; i <= m; ++i) {
        for (int j = 1; j <= n; ++j) {
            if (p[j - 1] == '.' || s[i - 1] == p[j - 1]) {
                dp[i][j] = dp[i - 1][j - 1];
            } else if (p[j - 1] == '*') {
                dp[i][j] = dp[i][j - 2] || (dp[i - 1][j] && (s[i - 1] == p[j - 2] || p[j - 2] == '.'));
            }
        }
    }

    // 返回结果
    return dp[m][n];
}

int main() {
    string s = "aaa";
    string p1 = "a.a";
    string p2 = "ab*ac*a";
    string p3 = "aa.a";
    string p4 = "ab*a";

    cout << "是否匹配：" << isMatch(s, p1) << endl; // true
    cout << "是否匹配：" << isMatch(s, p2) << endl; // true
    cout << "是否匹配：" << isMatch(s, p3) << endl; // false
    cout << "是否匹配：" << isMatch(s, p4) << endl; // false

    return 0;
}

16、最长的括号子串

16.1、问题描述

给出一个长度为 n 的，仅包含字符 '(' 和 ')' 的字符串，计算最长的格式正确的括号子串的长度。

例1: 对于字符串 "(()" 来说，最长的格式正确的子串是 "()" ，长度为 2 .

例2：对于字符串 ")()())" , 来说, 最长的格式正确的子串是 "()()" ，长度为 4 .

字符串长度：50≤n≤5∗105

要求时间复杂度O(n) ,空间复杂度O(n).

示例1
输入："(()"
返回值：2
示例2
输入："(())"
返回值：4

16.2、思路及代码

思路：

定义状态：使用一维数组 dp[i] 表示以字符串的第 i 个字符结尾的最长有效括号子串的长度。
初始化状态：所有的 dp[i] 初始值都为 0。
状态转移方程：
1. 如果 s[i] 是 (，则 dp[i] 必定为 0。
2. 如果 s[i] 是 )，分两种情况：
  - 如果 s[i-1] 是 (，则 dp[i] = dp[i-2] + 2。
  - 如果 s[i-1] 是 ) 且 i-dp[i-1]-1 处是 (，则 dp[i] = dp[i-1] + 2 + dp[i-dp[i-1]-2]。
遍历顺序：从左向右遍历字符串。
返回结果： dp 数组中的最大值即为最长有效括号子串的长度。

参考代码：

C++

#include <iostream>
#include <vector>

using namespace std;

int longestValidParentheses(string s) {
    int n = s.length();
    if (n <= 1) return 0;

    // 初始化动态规划数组
    vector<int> dp(n, 0);
    int maxLen = 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] > 0 && s[i - dp[i - 1] - 1] == '(') {
                dp[i] = dp[i - 1] + ((i - dp[i - 1]) >= 2 ? dp[i - dp[i - 1] - 2] : 0) + 2;
            }
            maxLen = max(maxLen, dp[i]);
        }
    }

    return maxLen;
}

int main() {
    string s1 = "(()";       // 输出: 2
    string s2 = ")()())";    // 输出: 4

    cout << "最长有效括号子串长度：" << longestValidParentheses(s1) << endl;
    cout << "最长有效括号子串长度：" << longestValidParentheses(s2) << endl;

    return 0;
}

17、打家劫舍(一)

17.1、问题描述

你是一个经验丰富的小偷，准备偷沿街的一排房间，每个房间都存有一定的现金，为了防止被发现，你不能偷相邻的两家，即，如果偷了第一家，就不能再偷第二家；如果偷了第二家，那么就不能偷第一家和第三家。

给定一个整数数组nums，数组中的元素表示每个房间存有的现金数额，请你计算在不被发现的前提下最多的偷窃金额。

示例1
输入：[1,2,3,4]
返回值：6
说明：最优方案是偷第 2，4 个房间
示例2
输入：[1,3,6]
返回值：7
说明：最优方案是偷第 1，3个房间
示例3
输入：[2,10,5]
返回值：10
说明：最优方案是偷第 2 个房间

17.2、思路及代码

思路：

定义状态：使用一维数组 dp，其中 dp[i] 表示在偷到第 i 家时的最大偷窃金额。
初始化状态：初始时，dp[0] = nums[0]，dp[1] = max(nums[0], nums[1])。
状态转移方程：对于每一家 i，有两种选择：
1. 如果偷第 i 家，那么 dp[i] = dp[i-2] + nums[i]。
2. 如果不偷第 i 家，那么 dp[i] = dp[i-1]。
遍历顺序：从前往后遍历。
返回结果： dp 数组中的最后一个元素即为最大偷窃金额。

参考代码：

C++

#include <iostream>
#include <vector>

using namespace std;

int rob(vector<int>& nums) {
    int n = nums.size();
    if (n == 0) return 0;
    if (n == 1) return nums[0];

    // 定义状态数组 dp，其中 dp[i] 表示偷到第 i 家时的最大偷窃金额
    vector<int> dp(n, 0);
    dp[0] = nums[0];
    dp[1] = max(nums[0], nums[1]);

    // 遍历每一家，计算最大偷窃金额
    for (int i = 2; i < n; ++i) {
        // 对于每一家 i，有两种选择：偷或者不偷
        // 如果偷第 i 家，dp[i] = dp[i-2] + nums[i]，否则 dp[i] = dp[i-1]
        dp[i] = max(dp[i-2] + nums[i], dp[i-1]);
    }

    // 返回最大偷窃金额
    return dp[n-1];
}

int main() {
    vector<int> nums = {2, 7, 9, 3, 1};

    // 调用 rob 函数计算最大偷窃金额
    int result = rob(nums);

    cout << "最大偷窃金额为：" << result << endl;

    return 0;
}

18、打家劫舍(二)

18.1、问题描述

你是一个经验丰富的小偷，准备偷沿湖的一排房间，每个房间都存有一定的现金，为了防止被发现，你不能偷相邻的两家，即，如果偷了第一家，就不能再偷第二家，如果偷了第二家，那么就不能偷第一家和第三家。沿湖的房间组成一个闭合的圆形，即第一个房间和最后一个房间视为相邻。

给定一个长度为n的整数数组nums，数组中的元素表示每个房间存有的现金数额，请你计算在不被发现的前提下最多的偷窃金额。

示例1
输入：[1,2,3,4]
返回值：6
说明：最优方案是偷第 2 4 个房间
示例2
输入：[1,3,6]
返回值：6
说明：由于 1 和 3 是相邻的，因此最优方案是偷第 3 个房间

18.2、思路及代码

思路：

由于房间形成了一个闭合的圆形，首尾房间被视为相邻，因此我们需要分两种情况来考虑：

偷第一家，不偷最后一家：这样问题就转化为了一个线性排列的房间，可以使用动态规划求解。
不偷第一家，偷最后一家：同样问题转化为线性排列，使用动态规划求解。

对于线性排列的房间，我们可以使用动态规划来计算最大偷窃金额。具体思路如下：

定义两个变量 dp_i_1 和 dp_i_2，分别表示截至当前房间的最大偷窃金额和前一个房间的最大偷窃金额。
对于当前房间 i，计算截至当前房间的最大偷窃金额 dp_i：
- dp_i = max(dp_i_1, dp_i_2 + nums[i])。
更新 dp_i_2 和 dp_i_1 的值。
最终的结果即为截至当前房间的最大偷窃金额。

参考代码：

C++

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int rob(vector<int>& nums) {
    int n = nums.size();
    if (n == 0) return 0;
    if (n == 1) return nums[0];
    
    // 由于房间形成了一个闭合的圆形，分两种情况考虑：
    // 1. 偷第一家，不偷最后一家
    // 2. 不偷第一家，偷最后一家

    // 定义辅助函数 robRange 计算闭合区间的最大偷窃金额
    auto robRange = [&](int start, int end) {
        int dp_i_1 = 0, dp_i_2 = 0;
        for (int i = start; i <= end; ++i) {
            int dp_i = max(dp_i_1, dp_i_2 + nums[i]);
            dp_i_2 = dp_i_1;
            dp_i_1 = dp_i;
        }
        return dp_i_1;
    };

    // 计算两种情况下的最大偷窃金额
    int result = max(robRange(0, n - 2), robRange(1, n - 1));

    return result;
}

int main() {
    vector<int> nums = {2, 3, 2};
    int result = rob(nums);
    cout << "最大偷窃金额为：" << result << endl;

    return 0;
}

19、买卖股票的最好时机(一)

19.1、问题描述

假设你有一个数组prices，长度为n，其中prices[i]是股票在第i天的价格，请根据这个价格数组，返回买卖股票能获得的最大收益

1.你可以买入一次股票和卖出一次股票，并非每天都可以买入或卖出一次，总共只能买入和卖出一次，且买入必须在卖出的前面的某一天

2.如果不能获取到任何利润，请返回0

3.假设买入卖出均无手续费

示例1
输入：[8,9,2,5,4,7,1]
返回值：5
说明：
在第3天(股票价格 = 2)的时候买入，在第6天(股票价格 = 7)的时候卖出，最大利润 = 7-2 = 5 ，不能选择在第2天买入，第3天卖出，这样就亏损7了；同时，你也不能在买入前卖出股票。
示例2
输入：[2,4,1]
返回值：2
示例3
输入：[3,2,1]
返回值：0

19.2、思路及代码

思路：

动态规划的状态定义：

定义一个一维数组 dp，其中 dp[i] 表示在第 i 天卖出股票时能获得的最大收益。

动态规划的状态转移方程：

对于每一天 i，计算 dp[i] 时，我们需要考虑两种情况：
- 不卖出股票，即维持前一天的状态：dp[i] = dp[i-1]。
- 卖出股票，即在前一天之前的某天买入，计算收益：dp[i] = prices[i] - min_price，其中 min_price 表示前面几天的最低股价。

最终的结果就是 dp 数组中的最大值。

参考代码：

C++

#include <vector>
#include <algorithm>
#include <iostream>

using namespace std;

int maxProfit(vector<int>& prices) {
    int n = prices.size();
    if (n <= 1) {
        return 0; // 无法获取任何利润
    }

    int min_price = prices[0]; // 记录前面几天的最低股价
    vector<int> dp(n, 0);

    for (int i = 1; i < n; ++i) {
        // 不卖出股票或卖出股票的两种情况取较大值
        dp[i] = max(dp[i - 1], prices[i] - min_price);
        // 更新前面几天的最低股价
        min_price = min(min_price, prices[i]);
    }

    return dp[n - 1];
}

int main() {
    vector<int> prices = {7,1,5,3,6,4};
    int result = maxProfit(prices);
    cout << "最大收益: " << result << endl; // 输出 5
    return 0;
}

20、买卖股票的最好时机(二)

20.1、问题描述

假设你有一个数组prices，长度为n，其中prices[i]是某只股票在第i天的价格，请根据这个价格数组，返回买卖股票能获得的最大收益

你可以多次买卖该只股票，但是再次购买前必须卖出之前的股票
如果不能获取收益，请返回0
假设买入卖出均无手续费

示例1
输入：[8,9,2,5,4,7,1]
返回值：7
说明：
在第1天(股票价格=8)买入，第2天(股票价格=9)卖出，获利9-8=1 在第3天(股票价格=2)买入，第4天(股票价格=5)卖出，获利5-2=3 在第5天(股票价格=4)买入，第6天(股票价格=7)卖出，获利7-4=3 总获利1+3+3=7，返回7
示例2
输入：[5,4,3,2,1]
返回值：0
说明：
由于每天股票都在跌，因此不进行任何交易最优。最大收益为0。
示例3
输入：[1,2,3,4,5]
返回值：4
说明：
第一天买进，最后一天卖出最优。中间的当天买进当天卖出不影响最终结果。最大收益为4。

20.2、思路及代码

思路：

动态规划的状态定义：

定义一个一维数组 dp，其中 dp[i] 表示在第 i 天卖出股票时能获得的最大收益。

动态规划的状态转移方程：

对于每一天 i，计算 dp[i] 时，我们需要考虑两种情况：
- 不卖出股票，即维持前一天的状态：dp[i] = dp[i-1]。
- 卖出股票，即在前一天之前的某天买入，计算收益：dp[i] = dp[i-1] + prices[i] - prices[i-1]。

最终的结果就是 dp 数组中的最大值。

参考代码：

C++

#include <vector>
#include <algorithm>
#include <iostream>

using namespace std;

int maxProfit(vector<int>& prices) {
    int n = prices.size();
    if (n <= 1) {
        return 0; // 无法获取任何利润
    }

    int max_profit = 0;

    for (int i = 1; i < n; ++i) {
        // 只要后一天的价格比前一天高，就进行交易
        if (prices[i] > prices[i - 1]) {
            max_profit += prices[i] - prices[i - 1];
        }
    }

    return max_profit;
}

int main() {
    vector<int> prices = {7,1,5,3,6,4};
    int result = maxProfit(prices);
    cout << "最大收益: " << result << endl; // 输出 7
    return 0;
}

21、买卖股票的最好时机(三)

21.1、问题描述

假设你有一个数组prices，长度为n，其中prices[i]是某只股票在第i天的价格，请根据这个价格数组，返回买卖股票能获得的最大收益。

你最多可以对该股票有两笔交易操作，一笔交易代表着一次买入与一次卖出，但是再次购买前必须卖出之前的股票
如果不能获取收益，请返回0
假设买入卖出均无手续费

示例1
输入：[8,9,3,5,1,3]
返回值：4
说明：
第三天(股票价格=3)买进，第四天(股票价格=5)卖出，收益为2 第五天(股票价格=1)买进，第六天(股票价格=3)卖出，收益为2 总收益为4。
示例2
输入：[9,8,4,1]
返回值：0
示例3
输入：[1,2,8,3,8]
返回值：12
说明：
第一笔股票交易在第一天买进，第三天卖出；第二笔股票交易在第四天买进，第五天卖出；总收益为12。因最多只可以同时持有一只股票，所以不能在第一天进行第一笔股票交易的买进操作，又在第二天进行第二笔股票交易的买进操作（此时第一笔股票交易还没卖出），最后两笔股票交易同时在第三天卖出，也即以上操作不满足题目要求。

21.2、思路及代码

思路：

定义一个三维数组 dp，其中 dp[i][k][j] 表示在第 i 天进行了 k 次交易（0 <= k <= 2），且当前状态为 j 时的最大收益。

动态规划的状态转移方程如下：

对于每一天 i，我们需要考虑两种情况：
1. 不进行交易，即维持前一天的状态：dp[i][k][0] = dp[i-1][k][0]。
2. 进行卖出操作，即在前一天之前的某天买入，计算收益：dp[i][k][1] = max(dp[i-1][k][1], dp[i-1][k-1][0] - prices[i])。
在进行买入操作时，我们需要考虑已经进行了 k 次交易的情况，即 dp[i-1][k-1][0]。

最终的结果是 dp 数组中的最大值。

参考代码：

C++

#include <vector>
#include <algorithm>
#include <iostream>

using namespace std;

int maxProfit(vector<int>& prices) {
    int n = prices.size();
    if (n <= 1) {
        return 0; // 无法获取任何利润
    }

    // 定义三维数组
    vector<vector<vector<int>>> dp(n, vector<vector<int>>(3, vector<int>(2, 0)));

    // 初始化状态
    dp[0][0][0] = 0;
    dp[0][0][1] = -prices[0];
    dp[0][1][0] = dp[0][1][1] = dp[0][2][0] = dp[0][2][1] = INT_MIN;

    // 遍历每一天
    for (int i = 1; i < n; ++i) {
        // 不进行交易
        dp[i][0][0] = dp[i-1][0][0];
        // 进行卖出操作
        dp[i][0][1] = max(dp[i-1][0][1], dp[i-1][0][0] - prices[i]);

        for (int k = 1; k <= 2; ++k) {
            // 不进行交易
            dp[i][k][0] = max(dp[i-1][k][0], dp[i-1][k][1] + prices[i]);
            // 进行卖出操作
            dp[i][k][1] = max(dp[i-1][k][1], dp[i-1][k-1][0] - prices[i]);
        }
    }

    // 取最大值作为最终结果
    return max({dp[n-1][0][0], dp[n-1][1][0], dp[n-1][2][0]});
}

int main() {
    vector<int> prices = {3,3,5,0,0,3,1,4};
    int result = maxProfit(prices);
    cout << "最大收益: " << result << endl; // 输出 6
    return 0;
}

微服务

文档

基础

动态规划 ​

1、斐波那契数列 ​

1.1、问题描述 ​

1.2、思路及代码 ​

1.2.1、递归 ​

1.2.2、动态规划 ​

2、跳台阶 ​

2.1、问题描述 ​

2.2、思路及代码 ​

2.2.1、递归 ​

2.2.2、动态规划 ​

3、最小花费爬楼梯 ​

3.1、问题描述 ​

3.2、思路及代码 ​

3.2.1、递归 ​

3.2.2、动态规划 ​

4、最长公共子序列(二) ​

4.1、问题描述 ​

4.2、思路及代码 ​

5、最长公共子串 ​

5.1、问题描述 ​

5.2、思路及代码 ​

6、不同路径的数目(一) ​

6.1、问题描述 ​

6.2、思路及代码 ​

7、矩阵的最小路径和 ​

7.1、问题描述 ​

7.2、思路及代码 ​

8、把数字翻译成字符串 ​

8.1、问题描述 ​

8.2、思路及代码 ​

9、兑换零钱(一) ​

9.1、问题描述 ​

9.2、思路及代码 ​

10、最长上升子序列(一) ​

10.1、问题描述 ​

10.2、思路及代码 ​

11、连续子数组的最大和 ​

11.1、问题描述 ​

11.2、思路及代码 ​

12、最长回文子串 ​

12.1、问题描述 ​

12.2、思路及代码 ​

13、数字字符串转化成IP地址 ​

13.1、问题描述 ​

13.2、思路及代码 ​

14、编辑距离(一) ​

14.1、问题描述 ​

14.2、思路及代码 ​

15、正则表达式匹配 ​

15.1、问题描述 ​

15.2、思路及代码 ​

动态规划

1、斐波那契数列

1.1、问题描述

1.2、思路及代码

1.2.1、递归

1.2.2、动态规划

2、跳台阶

2.1、问题描述

2.2、思路及代码

2.2.1、递归

2.2.2、动态规划

3、最小花费爬楼梯

3.1、问题描述

3.2、思路及代码

3.2.1、递归

3.2.2、动态规划

4、最长公共子序列(二)

4.1、问题描述

4.2、思路及代码

5、最长公共子串

5.1、问题描述

5.2、思路及代码

6、不同路径的数目(一)

6.1、问题描述

6.2、思路及代码

7、矩阵的最小路径和

7.1、问题描述

7.2、思路及代码

8、把数字翻译成字符串

8.1、问题描述

8.2、思路及代码

9、兑换零钱(一)

9.1、问题描述

9.2、思路及代码

10、最长上升子序列(一)

10.1、问题描述

10.2、思路及代码

11、连续子数组的最大和

11.1、问题描述

11.2、思路及代码

12、最长回文子串

12.1、问题描述

12.2、思路及代码

13、数字字符串转化成IP地址

13.1、问题描述

13.2、思路及代码

14、编辑距离(一)

14.1、问题描述

14.2、思路及代码

15、正则表达式匹配

15.1、问题描述

15.2、思路及代码