• 代码随想录笔记--动态规划篇

    目录

    1--动态规划理论基础

    2--斐波那契数

    3--爬楼梯

    4--使用最小花费爬楼梯

    5--不同路径

    6--不同路径II

    7--整数拆分

    8--不同的二叉搜索树

    9--背包问题

    10--打家劫舍

    11--打家劫舍II

    12--打家劫舍III

    13--买卖股票的最佳时机

    14--买卖股票的最佳时机II

    15--买卖股票的最佳时机III

    16--买卖股票的最佳时机IV

    17--买卖股票的最佳时机含冷冻期

    18--买卖股票的最佳时机含手续费

    19--最长递增子序列

    20--最长连续递增序列

    21--最长重复子数组

    22--最长公共子序列

    23--不相交的线

    24--最大子序和

    25--判断子序列

    26--不同的子序列

    27--两个字符串的删除操作

    28--编辑距离

    29--回文子串

    30--最长回文子序列

    1--动态规划理论基础

    动态规划经典问题：① 背包问题；② 打家劫舍；③ 股票问题； ④ 子序列问题；

    动态规划五部曲：

            ① 确定 dp 数组及其下标的含义；

            ② 确定递推公式；

            ③ 确定 dp 数组的初始化；

            ④ 确定遍历顺序，一般为从左到右；

            ⑤ 打印 dp 数组，一般用于检查；

    2--斐波那契数

    主要思路：

            经典动态规划，dp[i] 表示第 i 个数的斐波那契数；递推公式为：dp[i] = dp[i-1] + dp[i - 2]；初始化dp[0] = 1，dp[1] = 1；遍历顺序从左到右；

    1. #include 
    2. #include 
    3.  
    4. class Solution {
    5. public:
    6.     int fib(int n) {
    7.         if(n <= 1) return n;
    8.         std::vector<int> dp(n+1, 0);
    9.         dp[0] = 0; dp[1] = 1;
    10.         for(int i = 2; i <= n; i++){
    11.             dp[i] = dp[i - 1] + dp[i - 2];
    12.         }
    13.         return dp[n];
    14.     }
    15. };
    16.  
    17. int main(int argc, char argv[]){
    18.     int test = 2;
    19.     Solution S1;
    20.     int res = S1.fib(test);
    21.     std::cout << res << std::endl;
    22.     return 0;
    23. }

    3--爬楼梯

    主要思路：

            经典动态规划，dp[i] 表示到达第 i 阶楼梯的方法数；递推公式为 dp[i] = dp[i - 1] + dp[i - 2]；初始化dp[1] = 1, dp[2] = 2；遍历顺序从左到右；

    1. #include 
    2. #include 
    3.  
    4. class Solution {
    5. public:
    6.     int climbStairs(int n) {
    7.         if(n <= 2) return n; 
    8.         std::vector<int> dp(n+1, 0);
    9.         dp[1] = 1, dp[2] = 2;
    10.         for(int i = 3; i <= n; i++){
    11.             dp[i] = dp[i - 1] + dp[i - 2];
    12.         }
    13.         return dp[n];
    14.     }
    15. };
    16.  
    17. int main(int argc, char argv[]){
    18.     int n = 2;
    19.     Solution S1;
    20.     int res = S1.climbStairs(n); 
    21.     std::cout << res << std::endl;
    22.     return 0;
    23. }

    4--使用最小花费爬楼梯

    主要思路：

            dp[i] 表示到达第 i 阶楼梯需要的最小花费；初始化 dp[0] = 0, dp[1] = 0，因为可以从 0 和 1 出发，因此不需要花费；递推公式为 dp[i] = std::min(dp[i-1] + cost[i-1], dp[i-2] + cost[i-2])；默认从左到右遍历；

    1. #include 
    2. #include 
    3.  
    4. class Solution {
    5. public:
    6.     int minCostClimbingStairs(std::vector<int>& cost) {
    7.         std::vector<int> dp(cost.size()+1, 0); // 到达第i阶的最小花费
    8.         dp[0] = 0;
    9.         dp[1] = 0;
    10.         for(int i = 2; i <= cost.size(); i++){
    11.             dp[i] = std::min(cost[i-2]+dp[i-2], cost[i-1]+dp[i-1]);
    12.         }
    13.         return dp[cost.size()];
    14.     }
    15. };
    16.  
    17. int main(int argc, char argv[]){
    18.     // cost = [1,100,1,1,1,100,1,1,100,1]
    19.     std::vector<int> cost = {1, 100, 1, 1, 1, 100, 1, 1, 100, 1};
    20.     Solution S1;
    21.     int res = S1.minCostClimbingStairs(cost);
    22.     std::cout << res << std::endl;
    23.     return 0;
    24. }

    5--不同路径

    主要思路：

            dp[i][j] 表示到达 (i, j) 位置的路径数，初始化两个边界 dp[i][0] = 1，dp[0][j] = 1；状态转移方程为：dp[i][j] = dp[i-1][j] + dp[i][j-1]；遍历顺序为从上到下，从左到右；

    1. #include 
    2. #include 
    3.  
    4. class Solution {
    5. public:
    6.     int uniquePaths(int m, int n) {
    7.         std::vectorint>> dp(m, std::vector<int>(n, 0));
    8.         // 初始化
    9.         for(int i = 0; i < m; i++) dp[i][0] = 1;
    10.         for(int j = 0; j < n; j++) dp[0][j] = 1;
    11.         // 遍历
    12.         for(int r = 1; r < m; r++){
    13.             for(int c = 1; c < n; c++){
    14.                 dp[r][c] = dp[r-1][c] + dp[r][c-1];
    15.             }
    16.         }
    17.         return dp[m-1][n-1];
    18.     }
    19. };
    20.  
    21. int main(int argc, char argv[]){
    22.     // m = 3, n = 7
    23.     int m = 3, n = 7;
    24.     Solution S1;
    25.     int res = S1.uniquePaths(m, n);
    26.     std::cout << res << std::endl;
    27.     return 0;
    28. }

    6--不同路径II

    主要思路：

            与上题类似，dp[i][j] 表示到达 (i, j) 位置的路径数，初始化两个边界 dp[i][0] = 1，dp[0][j] = 1（确保边界没有障碍物，有障碍物初始化为0）；状态转移方程为：(i, j)不是障碍物则 dp[i][j] = dp[i-1][j] + dp[i][j-1]，(i, j)为障碍物则dp[i][j] = 0；遍历顺序为从上到下，从左到右；

    1. #include 
    2. #include 
    3.  
    4. class Solution {
    5. public:
    6.     int uniquePathsWithObstacles(std::vectorint>>& obstacleGrid) {
    7.         int m = obstacleGrid.size(), n = obstacleGrid[0].size();
    8.         if(obstacleGrid[m-1][n-1] == 1) return 0;
    9.         
    10.         std::vectorint>> dp(m, std::vector<int>(n, 0));
    11.         // 初始化
    12.         for(int i = 0; i < m && obstacleGrid[i][0] != 1; i++) dp[i][0] = 1;
    13.         for(int j = 0; j < n && obstacleGrid[0][j] != 1; j++) dp[0][j] = 1;
    14.         // 遍历
    15.         for(int r = 1; r < m; r++){
    16.             for(int c = 1; c < n; c++){
    17.                 if(obstacleGrid[r][c] == 1) dp[r][c] = 0; // 障碍
    18.                 else dp[r][c] = dp[r-1][c] + dp[r][c-1];
    19.             }
    20.         }
    21.         return dp[m-1][n-1];
    22.     }
    23. };
    24.  
    25. int main(int argc, char argv[]){
    26.     // obstacleGrid = [[0,0,0],[0,1,0],[0,0,0]]
    27.     std::vectorint>> test = {{0, 0, 0}, {0, 1, 0}, {0, 0, 0}};
    28.     Solution S1;
    29.     int res = S1.uniquePathsWithObstacles(test);
    30.     std::cout << res << std::endl;
    31.     return 0;
    32. }

    7--整数拆分

    主要思路：

            dp[i] 表示整数 i 拆分后的最大乘积；初始化dp[0] = 0, dp[1] = 0, dp[2] = 1; 状态转移方程为：dp[i] = max(dp[i], max(j*(i-j), j * dp[i-j]))；

    1. #include 
    2. #include 
    3.  
    4. class Solution {
    5. public:
    6.     int integerBreak(int n) {
    7.         std::vector<int> dp(n+1, 0);
    8.         // 初始化
    9.         dp[0] = 0, dp[1] = 0, dp[2] = 1;
    10.         // 遍历
    11.         for(int i = 3; i <= n; i++){
    12.             for(int j = 0; j <= i/2; j++){
    13.                 dp[i] = std::max(dp[i], std::max(j*(i-j), j * dp[i-j]));
    14.             }
    15.         }
    16.         return dp[n];
    17.     }
    18. };
    19.  
    20. int main(int argc, char argv[]){
    21.     // n = 10
    22.     int test = 10;
    23.     Solution S1;
    24.     int res = S1.integerBreak(test);
    25.     std::cout << res << std::endl;
    26.     return 0;
    27. }

    8--不同的二叉搜索树

    主要思路：

            dp[i] 表示由 i 个数字构成的不同二叉搜索树的数目；

            初始化：dp[0] = 1；

            状态转移方程：dp[i] += dp[j-1] * dp[i-j]，0 <= j <= i；其中 dp[j-1] 来构成 j 的左子树，dp[i-j] 来构成 j 的右子树；

             遍历顺序：两个 for 循环，第 1 个 for 循环遍历 1 - n，第二个 for 循环遍历 1 - i；

    1. #include 
    2. #include 
    3.  
    4. class Solution {
    5. public:
    6.     int numTrees(int n) {
    7. 		std::vector<int> dp(n+1, 0);
    8. 		// 初始化
    9. 		dp[0] = 1;
    10. 		// 遍历
    11. 		for(int i = 1; i <= n; i++){
    12. 			for(int j = 1; j <= i; j++){
    13. 				dp[i] += dp[j-1] * dp[i-j];
    14. 			}
    15. 		}
    16. 		return dp[n];
    17.     }
    18. };
    19.  
    20. int main(int argc, char *argv[]) {
    21. 	// n = 3
    22. 	int test = 3;
    23. 	Solution S1;
    24. 	int res = S1.numTrees(test);
    25. 	std::cout << res << std::endl;
    26. 	return 0;
    27. }

    9--背包问题

    背包问题笔记

    10--打家劫舍

    主要思路：

            基于动态规划，dp[i]表示截止到坐标 i 时，能够偷到的最高金额；

            初始化 dp[0] = nums[0], dp[1] = max(nums[0], nums[1])；

            状态转移方程：dp[i] = max(nums[i] + dp[i-2], dp[i-1])；dp[i-2] + nums[i] 表示偷索引为 i 的房屋，dp[i-1] 表示不偷索引为 i 的房屋；

    1. #include 
    2. #include 
    3.  
    4. class Solution {
    5. public:
    6.     int rob(std::vector<int>& nums) {
    7.         if(nums.size() == 1) return nums[0];
    8.         std::vector<int> dp(nums.size(), 0);
    9.         dp[0] = nums[0], dp[1] = std::max(nums[0], nums[1]);
    10.         for(int i = 2; i < nums.size(); i++){
    11.             dp[i] = std::max(dp[i-2] + nums[i], dp[i - 1]);
    12.         }
    13.         return dp[nums.size() - 1];
    14.     }
    15. };
    16.  
    17. int main(int argc, char argv[]){
    18.     std::vector<int> test = {1, 2, 3, 1};
    19.     Solution S1;
    20.     int res = S1.rob(test);
    21.     std::cout << res << std::endl;
    22.     return 0;
    23. }

    11--打家劫舍II

    主要思路：

            本题房屋围成一圈，因此首尾房屋不能同时打劫，将本题划分为三种情况：① 不打劫首尾房屋；② 考虑打劫首房屋，则不能打劫尾房屋；③ 考虑打劫尾房屋，则不能打劫首房屋；

    1. #include 
    2. #include 
    3.  
    4. class Solution {
    5. public:
    6.     int rob(std::vector<int>& nums) {
    7.         if(nums.size() == 1) return nums[0];
    8.         // 不考虑首尾房屋
    9.         std::vector<int> nums1(nums.begin() + 1, nums.end() - 1);
    10.         // 考虑首房屋
    11.         std::vector<int> nums2(nums.begin(), nums.end() - 1);
    12.         // 考虑尾房屋
    13.         std::vector<int> nums3(nums.begin() + 1, nums.end());
    14.  
    15.         return std::max(std::max(dp_solution(nums1), dp_solution(nums2)), dp_solution(nums3));
    16.     }
    17.  
    18.     int dp_solution(std::vector<int>& nums){ // 打家劫舍I的代码
    19.         if(nums.size() == 0) return 0;
    20.         if(nums.size() == 1) return nums[0];
    21.         std::vector<int> dp(nums.size(), 0);
    22.         dp[0] = nums[0], dp[1] = std::max(nums[0], nums[1]);
    23.         for(int i = 2; i < nums.size(); i++){
    24.             dp[i] = std::max(dp[i-2] + nums[i], dp[i - 1]);
    25.         }
    26.         return dp[nums.size() - 1];
    27.     }
    28. };
    29.  
    30. int main(int argc, char argv[]){
    31.     std::vector<int> test = {2, 3, 2};
    32.     Solution S1;
    33.     int res = S1.rob(test);
    34.     std::cout << res << std::endl;
    35.     return 0;
    36. }

    12--打家劫舍III

    主要思路：

            基于二叉树递归（后序遍历）和动态规划，每个节点拥有两个状态，dp[0] 表示不打劫当前节点的最高金额，dp[1] 表示打劫当前节点的最高金额；

            对于每个节点 cur，dp[1]  = dp_left[0] + dp_right[0] + cur->val，即打劫当前节点时，不能打劫左孩子和右孩子；

            dp[0] = std::max(dp_left[0], dp_left[1]) + std::max(dp_right[0], dp_right[1])；不打劫当前节点时，可以打劫也可以不打劫左右孩子，取两种情况的最大值；

    1. #include 
    2. #include 
    3.  
    4. struct TreeNode {
    5.     int val;
    6.     TreeNode *left;
    7.     TreeNode *right;
    8.     TreeNode() : val(0), left(nullptr), right(nullptr) {}
    9.     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
    10.     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
    11. };
    12.  
    13. class Solution {
    14. public:
    15.     int rob(TreeNode* root) {
    16.         std::vector<int> res = dfs(root);
    17.         return std::max(res[0], res[1]);
    18.     }
    19.  
    20.     std::vector<int> dfs(TreeNode* cur){
    21.         if(cur == nullptr) return {0, 0};
    22.         std::vector<int> dp_left = dfs(cur->left);
    23.         std::vector<int> dp_right = dfs(cur->right);
    24.  
    25.         int dp_cur0 = std::max(dp_left[0], dp_left[1]) + std::max(dp_right[0], dp_right[1]);
    26.         int dp_cur1 = dp_left[0] + dp_right[0] + cur->val;
    27.         return {dp_cur0, dp_cur1};
    28.     }
    29. };
    30.  
    31. int main(int argc, char argv[]){
    32.     // root = [3, 2, 3, null, 3, null, 1]
    33.     TreeNode *Node1 = new TreeNode(3);
    34.     TreeNode *Node2 = new TreeNode(2);
    35.     TreeNode *Node3 = new TreeNode(3);
    36.     TreeNode *Node4 = new TreeNode(3);
    37.     TreeNode *Node5 = new TreeNode(1);
    38.  
    39.     Node1->left = Node2;
    40.     Node1->right = Node3;
    41.     Node2->right = Node4;
    42.     Node3->right = Node5;
    43.  
    44.     Solution S1;
    45.     int res = S1.rob(Node1);
    46.     std::cout << res << std::endl;
    47.  
    48.     return 0;
    49. }

    13--买卖股票的最佳时机

    主要思路：

            每一天都有两个状态：即持有股票和不持有股票；

            dp[i][0] 表示第 i 天持有股票时的最大金额，dp[i][1] 表示第 i 天不持有股票时的最大金额；

            状态转移方程：dp[i][0] = max(dp[i-1][0], 0-prices[i])；dp[i][1] = max(dp[i-1][1], dp[i-1][0] + prices[1])；

            初始化 dp[0][0] = -prices[0], dp[i][1] = 0；

    1. #include 
    2. #include 
    3.  
    4. class Solution {
    5. public:
    6.     int maxProfit(std::vector<int>& prices) {
    7.         std::vectorint>> dp(prices.size(), std::vector<int>(2, 0));
    8.         dp[0][0] = -prices[0], dp[0][1] = 0;
    9.         for(int i = 1; i < prices.size(); i++){
    10.             dp[i][0] = std::max(dp[i-1][0], -prices[i]);
    11.             dp[i][1] = std::max(dp[i-1][1], dp[i-1][0] + prices[i]);
    12.         }
    13.         return dp[prices.size() - 1][1];
    14.     }
    15. };
    16.  
    17. int main(int argc, char argv[]){
    18.     // [7, 1, 5, 3, 6, 4]
    19.     std::vector<int> test = {7, 1, 5, 3, 6, 4};
    20.     Solution S1;
    21.     int res = S1.maxProfit(test);
    22.     std::cout << res << std::endl;
    23.     return 0;
    24. }

    14--买卖股票的最佳时机II

    主要思路：

            每一天都有两个状态：即持有股票和不持有股票；

            dp[i][0] 表示第 i 天持有股票时的最大金额，dp[i][1] 表示第 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-1][0] + prices[1])；

            由于可以多次买卖，则第 i 天持有股票的状态可能由第 i-1 天不持有股票，在第 i 天买入股票推导而得；

            初始化dp[0][0] = -prices[0]，dp[0][1] = 0；

    1. #include 
    2. #include 
    3.  
    4. class Solution {
    5. public:
    6.     int maxProfit(std::vector<int>& prices) {
    7.         std::vectorint>> dp(prices.size(), std::vector<int>(2, 0));
    8.         dp[0][0] = -prices[0], dp[0][1] = 0;
    9.         for(int i = 1; i < prices.size(); i++){
    10.             dp[i][0] = std::max(dp[i-1][0], dp[i-1][1] - prices[i]);
    11.             dp[i][1] = std::max(dp[i-1][1], dp[i-1][0] + prices[i]);
    12.         }
    13.         return dp[prices.size() - 1][1];
    14.     }
    15. };
    16.  
    17. int main(int argc, char argv[]){
    18.     // [7, 1, 5, 3, 6, 4]
    19.     std::vector<int> test = {7, 1, 5, 3, 6, 4};
    20.     Solution S1;
    21.     int res = S1.maxProfit(test);
    22.     std::cout << res << std::endl;
    23.     return 0;
    24. }

    15--买卖股票的最佳时机III

    主要思路：

            本题最多只能买卖两次，则对于每一天，会有以下五种状态：dp[i][0] 表示第 i 天不进行任何操作，dp[i][1] 表示第 i 天第一次买入，dp[i][2] 表示第 i 天第一次卖出，dp[i][3] 表示第 i 天第二次买入，dp[i][4] 表示第 i 天第二次卖出；

            状态转移方程：dp[i][0] = dp[i-1][0]，dp[i][1] = max(dp[i-1][1], dp[i-1][0] - prices[i])；

            dp[i][2] = max(dp[i-1][2], dp[i-1][1] + prices[i])；

            dp[i][3] = max(dp[i-1][3], dp[i-1][2] - prices[i])；

            dp[i][4] = max(dp[i-1][4], dp[i-1][3] + prices[i])；

            初始化：dp[0][0] = 0，dp[0][1] = -prices[0]，dp[0][2] = 0，dp[0][3] = -prices[0]，dp[0][4] = 0；

    1. #include 
    2. #include 
    3.  
    4. class Solution {
    5. public:
    6.     int maxProfit(std::vector<int>& prices) {
    7.         std::vectorint>> dp(prices.size(), std::vector<int>(5, 0));
    8.         dp[0][0] = 0, dp[0][1] = -prices[0], dp[0][2] = 0, dp[0][3] = -prices[0], dp[0][4] = 0;
    9.         for(int i = 1; i < prices.size(); i++){
    10.             dp[i][0] = dp[i-1][0];
    11.             dp[i][1] = std::max(dp[i-1][1], dp[i-1][0] - prices[i]);
    12.             dp[i][2] = std::max(dp[i-1][2], dp[i-1][1] + prices[i]);
    13.             dp[i][3] = std::max(dp[i-1][3], dp[i-1][2] - prices[i]);
    14.             dp[i][4] = std::max(dp[i-1][4], dp[i-1][3] + prices[i]);
    15.  
    16.         }
    17.         return dp[prices.size() - 1][4];
    18.     }
    19. };
    20.  
    21. int main(int argc, char argv[]){
    22.     // [3, 3, 5, 0, 0, 3, 1, 4]
    23.     std::vector<int> test = {3, 3, 5, 0, 0, 3, 1, 4};
    24.     Solution S1;
    25.     int res = S1.maxProfit(test);
    26.     std::cout << res << std::endl;
    27.     return 0;
    28. }

    16--买卖股票的最佳时机IV

    主要思路：

            类似于上题，上题中最多可以买卖两次，对应五种状态；本题最多可以买卖k次，对应2K+1种状态。

            状态转移方程与初始化类似于上题。

    1. #include 
    2. #include 
    3.  
    4. class Solution {
    5. public:
    6.     int maxProfit(int k, std::vector<int>& prices) {
    7.         std::vectorint>> dp(prices.size(), std::vector<int>(2*k+1, 0));
    8.         // 初始化
    9.         for(int j = 1; j < 2*k+1; j += 2){
    10.             dp[0][j] = -prices[0]; // 持有
    11.             dp[0][j+1] = 0;  // 不持有     
    12.         }
    13.         // 递推
    14.         for(int i = 1; i < prices.size(); i++){
    15.             for(int j = 1; j < 2*k+1; j += 2){
    16.                 dp[i][j] = std::max(dp[i-1][j], dp[i][j - 1] - prices[i]); // 持有
    17.                 dp[i][j+1] = std::max(dp[i-1][j+1], dp[i][j] + prices[i]); // 不持有
    18.             }
    19.         }
    20.         return dp[prices.size() - 1][2*k];
    21.     }
    22. };
    23.  
    24. int main(int argc, char *argv[]) {
    25.     // k = 2, prices = [2,4,1]
    26.     int k = 2;
    27.     std::vector<int> prices = {2, 4, 1};
    28.     Solution S1;
    29.     int res = S1.maxProfit(k, prices);
    30.     std::cout << res << std::endl;
    31. }

    17--买卖股票的最佳时机含冷冻期

    主要思路：

            将第 i 天拆分为四种状态：dp[i][0] 表示持有股票，dp[i][1] 表示保持卖出股票状态（冷冻期的下一天），dp[i][2] 表示卖出股票，dp[i][3] 表示冷冻期（卖出股票的下一天）。

    状态转移方程：

            dp[i][0] = max(dp[i-1][0], dp[i-1][1] - prices[i], dp[i-1][3] - prices[i]);

            dp[i][1] = max(dp[i-1][1], dp[i-1][3]);

            dp[i][2] = dp[i-1][0] + prices[i];

            dp[i][3] = dp[i-1][2]

    初始化：

            dp[0][0] = -prices[0], dp[0][1] = 0, dp[0][2] = 0, dp[0][3] = 0；对于不能直接推导出初始化值的状态，可以根据状态转移方程的合理性来推导，即把数据代入到状态转移方程，得出初始化结果。

    1. #include 
    2. #include 
    3.  
    4. class Solution {
    5. public:
    6.     int maxProfit(std::vector<int>& prices) {
    7.         std::vectorint>>dp(prices.size(), std::vector<int>(4, 0));
    8.         // 初始化
    9.         dp[0][0] = -prices[0], dp[0][1] = 0, dp[0][2] = 0, dp[0][3] = 0;
    10.         for(int i = 1; i < prices.size(); i++){
    11.             // 状态转移
    12.             dp[i][0] = std::max(std::max(dp[i-1][0], dp[i-1][1] - prices[i]), dp[i-1][3] - prices[i]); // 持有股票可以是前一天就持有股票；也可以是前一天是保持卖出状态，然后当天买入股票；还可以前一天是冷冻期，然后当天买入股票；
    13.             dp[i][1] = std::max(dp[i-1][1], dp[i-1][3]); // 保持卖出股票的状态，前一天可以是保持卖出股票的状态，前一天也可以是冷冻期
    14.             dp[i][2] = dp[i-1][0] + prices[i]; // 卖出股票，前一天只能是持有股票
    15.             dp[i][3] = dp[i-1][2]; // 冷冻期，前一天只能是卖出股票
    16.         }
    17.         // 不持有股票
    18.         return std::max(std::max(dp[prices.size() - 1][1], dp[prices.size() - 1][2]), dp[prices.size() - 1][3]);
    19.     }
    20. };
    21.  
    22. int main(int argc, char argv[]){
    23.     // prices = [1,2,3,0,2]
    24.     std::vector<int> test = {1, 2, 3, 0, 2};
    25.     Solution S1;
    26.     int res = S1.maxProfit(test);
    27.     std::cout << res << std::endl;
    28.     return 0;
    29. }

    18--买卖股票的最佳时机含手续费

    主要思路：

            与买卖股票的最佳时机II类似，只是在卖出股票的时候需要减去对应的手续费。

    1. #include 
    2. #include 
    3.  
    4. class Solution {
    5. public:
    6.     int maxProfit(std::vector<int>& prices, int fee) {
    7.         // 持有股票和不持有股票两种状态
    8.         std::vectorint>> dp(prices.size(), std::vector<int>(2, 0)); 
    9.         dp[0][0] = -prices[0]; // 持有股票
    10.         dp[0][1] = 0; // 不持有股票 // 这里可能会误初始化为 -fee，但考虑实际价值如果当天买入就卖出，白亏一笔手续费，所以干脆不买，初始化为0
    11.         for(int i = 1; i < prices.size(); i++){
    12.             dp[i][0] = std::max(dp[i-1][0], dp[i-1][1] - prices[i]);
    13.             dp[i][1] = std::max(dp[i-1][1], dp[i-1][0] + prices[i] - fee);
    14.         }
    15.         return dp[prices.size() - 1][1];
    16.     }
    17. };
    18.  
    19. int main(int argc, char argv[]){
    20.     // prices = [1, 3, 2, 8, 4, 9], fee = 2
    21.     std::vector<int> test = {1, 3, 2, 8, 4, 9};
    22.     int fee = 2;
    23.     Solution S1;
    24.     int res = S1.maxProfit(test, fee);
    25.     std::cout << res << std::endl;
    26.     return 0;
    27. }

    19--最长递增子序列

    主要思路：

            dp[i] 表示以字母 nums[i] 结尾的最长子序列长度；

            状态转移方程：当 j  < i 且 nums[j] < nums[i] 时，nums[i] = std::max(dp[i], dp[j] + 1);

    1. #include 
    2. #include 
    3.  
    4. class Solution {
    5. public:
    6.     int lengthOfLIS(std::vector<int>& nums) {
    7.         std::vector<int> dp(nums.size(), 1); // 初始化为1，至少是以自己作为结尾，其最小长度是1
    8.         int res = 1;
    9.         for(int i = 1; i < nums.size(); i++){
    10.             for(int j = 0; j < i; j++){
    11.                 if(nums[j] < nums[i]){
    12.                     dp[i] = std::max(dp[i], dp[j] + 1);
    13.                 }
    14.             }
    15.             if (dp[i] > res) res = dp[i]; // 记录最长的长度
    16.         }
    17.         return res;
    18.     }
    19. };
    20.  
    21. int main(int argc, char argv[]){
    22.     // nums = [10, 9, 2, 5, 3, 7, 101, 18]
    23.     std::vector<int> test = {10, 9, 2, 5, 3, 7, 101, 18};
    24.     Solution S1;
    25.     int res = S1.lengthOfLIS(test);
    26.     std::cout << res << std::endl;
    27.     return 0;
    28. }

    20--最长连续递增序列

    主要思路：

            与上题类似，但本题要求连续递增的子序列，因此不需要遍历索引为[0, i）的数值，只需要判断前面一个数值；

    1. #include 
    2. #include 
    3.  
    4. class Solution {
    5. public:
    6.     int findLengthOfLCIS(std::vector<int>& nums) {
    7.         std::vector<int> dp(nums.size(), 1);
    8.         int res = 1;
    9.         for(int i = 1; i < nums.size(); i++){
    10.             if(nums[i-1] < nums[i]) dp[i] = std::max(dp[i], dp[i-1] + 1);
    11.             if(dp[i] > res) res = dp[i];
    12.         }
    13.         return res;
    14.     }
    15. };
    16.  
    17. int main(int argc, char argv[]){
    18.     // nums = [1, 3, 5, 4, 7]
    19.     std::vector<int> test = {1, 3, 5, 4, 7};
    20.     Solution S1;
    21.     int res = S1.findLengthOfLCIS(test);
    22.     std::cout << res << std::endl;
    23.     return 0;
    24. }

    21--最长重复子数组

    主要思路：

           dp[i][j] 表示以 nums1[i] 和 nums2[j] 结尾的, 公共的长度最长的子数组的长度；

    1. #include 
    2. #include 
    3.  
    4. class Solution {
    5. public:
    6.     int findLength(std::vector<int>& nums1, std::vector<int>& nums2) {
    7.         // dp[i][j] 表示以 nums1[i] 和 nums2[j]结尾的, 公共的长度最长的子数组的长度 
    8.         std::vectorint>> dp(nums1.size(), std::vector<int>(nums2.size(), 0));
    9.  
    10.         int res = 0;
    11.         // 初始化
    12.         for(int i = 0; i < nums1.size(); i++){
    13.             if(nums1[i] == nums2[0]){
    14.                 res = 1;
    15.                 dp[i][0] = 1;
    16.             }
    17.         }
    18.         for(int j = 0; j < nums2.size(); j++){
    19.             if(nums1[0] == nums2[j]){
    20.                 res = 1;
    21.                 dp[0][j] = 1;
    22.             }
    23.         }
    24.         // 状态转移
    25.         for(int i = 1; i < nums1.size(); i++){
    26.             for(int j = 1; j < nums2.size(); j++){
    27.                 if(nums1[i] == nums2[j]) dp[i][j] = dp[i - 1][j - 1] + 1;
    28.                 if (dp[i][j] > res) res = dp[i][j];
    29.             }
    30.         }
    31.         return res;
    32.     }
    33. };
    34.  
    35. int main(int argc, char *argv[]) {
    36.     // nums1 = [1,2,3,2,1], nums2 = [3,2,1,4,7]
    37.     std::vector<int> nums1 = {1, 2, 3, 2, 1};
    38.     std::vector<int> nums2 = {3, 2, 1, 4, 7};
    39.     Solution S1;
    40.     int res = S1.findLength(nums1, nums2);
    41.     std::cout << res << std::endl;
    42.     return 0;
    43. }

    22--最长公共子序列

    主要思路：

            dp[i][j]表示在 text1 [0, i] 和 text2 [0, j] 范围内最长的公共子序列长度；

    状态转移方程：

            text1[i] == text2[j] 时，dp[i][j] = dp[i-1][j-1] + 1；

            text1[i] != text2[j] 时, dp[i][j] = std::max(dp[i-1][j], dp[i][j-1])；即取[0, i] [0, j-1] 和 [0, i-1][0, j]的最大值；

    1. #include 
    2. #include 
    3. #include 
    4.  
    5. class Solution {
    6. public:
    7.     int longestCommonSubsequence(std::string text1, std::string text2){
    8.         // dp[i][j]表示在 text1 [0, i] 和 text2 [0, j] 范围内最长的公共子序列长度
    9.         std::vectorint>> dp(text1.length(), std::vector<int>(text2.length(), 0));   
    10.         // 初始化
    11.         for(int i = 0; i < text1.length(); i++){
    12.             if(text1[i] == text2[0]){
    13.                 dp[i][0] = 1; 
    14.             }
    15.             else if(i > 0){
    16.                 dp[i][0] = dp[i-1][0];
    17.             }
    18.         }
    19.         for(int j = 0; j < text2.length(); j++){
    20.             if(text1[0] == text2[j]){
    21.                 dp[0][j] = 1;
    22.             }
    23.             else if(j > 0){
    24.                 dp[0][j] = dp[0][j-1];
    25.             }
    26.         }
    27.         // 状态转移
    28.         for(int i = 1; i < text1.length(); i++){
    29.             for(int j = 1; j < text2.length(); j++){
    30.                 if(text1[i] == text2[j]){
    31.                     dp[i][j] = dp[i-1][j-1] + 1;        
    32.                 }
    33.                 else{
    34.                     dp[i][j] = std::max(dp[i-1][j], dp[i][j-1]);
    35.                 }
    36.             }
    37.         }        
    38.         return dp[text1.length() - 1][text2.length() - 1];
    39.     }
    40. };
    41.  
    42. int main(int argc, char *argv[]) {
    43.     // text1 = "abcde", text2 = "ace"
    44.     std::string str1 = "abcde";
    45.     std::string str2 = "ace";
    46.     Solution S1;
    47.     int res = S1.longestCommonSubsequence(str1, str2);
    48.     std::cout << res << std::endl;
    49.     return 0;
    50. }

    23--不相交的线

    主要思路：

            本题等价于求两个序列的最长公共子序列；

    1. #include 
    2. #include 
    3.  
    4. class Solution {
    5. public:
    6.     int maxUncrossedLines(std::vector<int>& nums1, std::vector<int>& nums2) {
    7.         std::vectorint>> dp(nums1.size(), std::vector<int>(nums2.size(), 0));
    8.         for(int i = 0; i < nums1.size(); i++){
    9.             if(nums1[i] == nums2[0]) dp[i][0] = 1;
    10.             else if(i > 0) dp[i][0] = dp[i-1][0];
    11.         }
    12.         for(int j = 0; j < nums2.size(); j++){
    13.             if(nums1[0] == nums2[j]) dp[0][j] = 1;
    14.             else if(j > 0) dp[0][j] = dp[0][j-1];
    15.         }
    16.         for(int i = 1; i < nums1.size(); i++){
    17.             for(int j = 1; j < nums2.size(); j++){
    18.                 if(nums1[i] == nums2[j]) dp[i][j] = dp[i-1][j-1] + 1;
    19.                 else dp[i][j] = std::max(dp[i-1][j], dp[i][j-1]);
    20.             }
    21.         }
    22.         return dp[nums1.size() - 1][nums2.size() - 1];
    23.     }
    24. };
    25.  
    26. int main(int argc, char argv[]){
    27.     // nums1 = [1,4,2], nums2 = [1,2,4]
    28.     std::vector<int> nums1 = {1, 4, 2}, nums2 = {1, 2, 4};
    29.     Solution S1;
    30.     int res = S1.maxUncrossedLines(nums1, nums2);
    31.     std::cout << res << std::endl;
    32.     return 0;
    33. }

    24--最大子序和

    主要思路：

            dp[i] 表示以 nums[i] 结尾的最大连续子数组的和；

            dp[i] = std::max(dp[i-1] + nums[i], nums[i]);

    1. #include 
    2. #include 
    3.  
    4. class Solution {
    5. public:
    6.     int maxSubArray(std::vector<int>& nums) {
    7.         std::vector<int> dp(nums.size(), 0);
    8.         int max = nums[0];
    9.         dp[0] = nums[0];
    10.         for(int i = 1; i < nums.size(); i++){
    11.             dp[i] = std::max(dp[i-1] + nums[i], nums[i]);
    12.             if(dp[i] > max) max = dp[i];
    13.         }
    14.         return max;
    15.     }
    16. };
    17.  
    18. int main(int argc, char argv[]){
    19.     // nums = [-2,1,-3,4,-1,2,1,-5,4]
    20.     std::vector<int> nums = {-2, 1, -3, 4, -1, 2, 1, -5, 4};
    21.     Solution S1;
    22.     int res = S1.maxSubArray(nums);
    23.     std::cout << res << std::endl;
    24.     return 0;
    25. }

    25--判断子序列

    主要思路：

            与最长公共子序列类似，只需要判断最长公共子序列是否等于 s 字符串的长度即可；

            即 dp[s.length() - 1][t.length() - 1] 是否等于 s.length()；

    1. #include 
    2. #include 
    3.  
    4. class Solution {
    5. public:
    6.     bool isSubsequence(std::string s, std::string t) {
    7.         if(s.length() == 0) return true;
    8.         if(t.length() == 0 && s.length() != 0) return false;
    9.         std::vectorint>> dp(s.length(), std::vector<int>(t.length(), 0));
    10.         for(int j = 0; j < t.length(); j++){
    11.             if(s[0] == t[j]) dp[0][j] = 1;
    12.             else if(j > 0) dp[0][j] = dp[0][j-1];
    13.         }
    14.         for(int i = 1; i < s.length(); i++){
    15.             for(int j = 1; j < t.length(); j++){
    16.                 if(s[i] == t[j]) dp[i][j] = dp[i-1][j-1] + 1;
    17.                 else dp[i][j] = dp[i][j-1];
    18.             }
    19.         }
    20.         if(dp[s.length() - 1][t.length() - 1] == s.length()) return true;
    21.         else return false;
    22.     }
    23. };
    24.  
    25. int main(int argc, char argv[]){
    26.     // s = "abc", t = "ahbgdc"
    27.     std::string str1 = "abc", str2 = "ahbgdc";
    28.     Solution S1;
    29.     bool res = S1.isSubsequence(str1, str2);
    30.     if(res) std::cout << "true" << std::endl;
    31.     else std::cout << "false" << std::endl;
    32.     return 0;
    33. }

    26--不同的子序列

    主要思路：

           本题可以转化为有多少种删除的方式，可以将字符串s转化为字符串t；

            定义 dp[i][j] 表示以字符串s中第i个字符结尾，通过删除s中字符，构成t中前j个字符（以第j个字符结尾）的方式的个数； 

            当s[i] = t[j] 时，dp[i][j] = dp[i-1][j-1] + dp[i-1][j]；加上dp[i-1][j]的原因是，可以不使用s[i]字符，由前i-1个字符来构成t的前j个字符；

    1. #include 
    2. #include 
    3.  
    4. class Solution {
    5. public:
    6.     int numDistinct(std::string s, std::string t) {
    7.         std::vectorint>> dp(s.length(), std::vector<int>(t.length(), 0));
    8.         if(s[0] == t[0]) dp[0][0] = 1;
    9.         for(int i = 1; i < s.length(); i++){
    10.             if(s[i] == t[0]) dp[i][0] = dp[i-1][0] + 1;
    11.             else dp[i][0] = dp[i-1][0];
    12.         }
    13.         for(int i = 1; i < s.length(); i++){
    14.             for(int j = 1; j < t.length(); j++){
    15.                 if(s[i] == t[j]) dp[i][j] = (dp[i-1][j-1] + dp[i-1][j]) % 1000000007;
    16.                 else dp[i][j] = dp[i-1][j]; // 用s中前i-1个字符来构成t中的前j个字符
    17.             }
    18.         }
    19.         return dp[s.length() - 1][t.length() - 1] % 1000000007;
    20.     }
    21. };
    22.  
    23. int main(int argc, char argv[]){
    24.     // s = "rabbbit", t = "rabbit"
    25.     std::string str1 = "rabbbit", str2 = "rabbit";
    26.     Solution S1;
    27.     int res = S1.numDistinct(str1, str2);
    28.     std::cout << res << std::endl;
    29.     return 0;
    30. }

    27--两个字符串的删除操作

    主要思路：

            基于动态规划，dp[i][j]表示以单词word1中第[i-1]字符结尾，word2中第[j-1]字符结尾，使得word1和word2相同所需的最小步数。

            当word[i-1]==word2[j-1]时，dp[i][j] = dp[i-1][j-1]；

            当word[i-1] != word2[j-1]时，dp[i][j] = std::min(dp[i-1][j] + 1, dp[i][j-1] + 1, dp[i-1][j-1] + 2);

    1. #include 
    2. #include 
    3. #include 
    4.  
    5. class Solution {
    6. public:
    7.     int minDistance(std::string word1, std::string word2) {
    8.         std::vectorint>>dp(word1.size() + 1, std::vector<int>(word2.size() + 1, 0));
    9.         // 初始化
    10.         for(int i = 1; i <= word1.size(); i++){
    11.             dp[i][0] = i;
    12.         }
    13.         for(int j = 1; j <= word2.size(); j++){
    14.             dp[0][j] = j;
    15.         }
    16.         for(int i = 1; i <= word1.size(); i++){
    17.             for(int j = 1; j <= word2.size(); j++){
    18.                 if(word1[i-1] == word2[j-1]) dp[i][j] = dp[i-1][j-1];
    19.                 else{
    20.                     dp[i][j] = std::min(dp[i-1][j] + 1, std::min(dp[i][j-1] + 1, dp[i-1][j-1] + 2));
    21.                 }
    22.             }
    23.         }
    24.         return dp[word1.size()][word2.size()];
    25.     }
    26. };
    27.  
    28. int main(int argc, char *argv[]){ 
    29.     // word1 = "sea", word2 = "eat"
    30.     std::string word1 = "sea";
    31.     std::string word2 = "eat";
    32.     Solution S1;
    33.     int res = S1.minDistance(word1, word2);
    34.     std::cout << res << std::endl;
    35.  
    36.     return 0;
    37. }

    28--编辑距离

    主要思路：

            dp[i][j] 表示使得word1[0, i-1]和word2[0, j-1]相等的最少操作次数；

            当 word1[i-1] 不等于 word2[j-1] 时，dp[i][j] = std::min(dp[i-1][j-1] + 1, std::min(dp[i-1][j] + 1, dp[i][j-1] + 1))；

    1. #include 
    2. #include 
    3. #include 
    4.  
    5. class Solution {
    6. public:
    7.     int minDistance(std::string word1, std::string word2) {
    8.         // dp[i][j] 表示使得word1[0, i-1]和word2[0, j-1]相等的最少操作次数
    9.         std::vectorint>> dp(word1.length() + 1, std::vector<int>(word2.length()+1, 0));
    10.         // 初始化
    11.         for(int i = 1; i <= word1.length(); i++){
    12.             dp[i][0] = i; // word2为空串
    13.         }
    14.         for(int j = 1; j <= word2.length(); j++){
    15.             dp[0][j] = j; // word1为空串
    16.         }
    17.  
    18.         for(int i = 1; i <= word1.length(); i++){
    19.             for(int j = 1; j <= word2.length(); j++){
    20.                 if(word1[i-1] == word2[j-1]) dp[i][j] = dp[i-1][j-1];
    21.                 else{
    22.                     // dp[i-1][j-1] + 1 表示替换操作
    23.                     // dp[i-1][j] + 1 表示删除word1[i-1]
    24.                     // dp[i][j-1] + 1 表示增加word1[i-1] 
    25.                     dp[i][j] = std::min(dp[i-1][j-1] + 1, std::min(dp[i-1][j] + 1, dp[i][j-1] + 1));
    26.                 }
    27.             }
    28.         }
    29.         return dp[word1.length()][word2.length()];
    30.     }
    31. };
    32.  
    33. int main(int argc, char argv[]){
    34.     // word1 = "horse", word2 = "ros"
    35.     std::string word1 = "horse";
    36.     std::string word2 = "ros";
    37.     Solution S1;
    38.     int res = S1.minDistance(word1, word2);
    39.     std::cout << res << std::endl;
    40.     return 0;
    41. }

    29--回文子串

    主要思路：

            起始本题更适合用双指针来做，动态规划可以参考代码随想录的思路:回文子串

            布尔类型的dp[i][j]：表示区间范围[i,j] （注意是左闭右闭）的子串是否是回文子串；

    30--最长回文子序列

    主要思路：

            dp[i][j]表示在s[i, j]范围内的最长回文子串；

    状态转移

            s[i] == s[j]时，dp[i][j] = dp[i+1][j-1] + 2

            s[i] != s[j]时，dp[i][j] = max(dp[i+1][j], dp[i][j-1])

            dp[i+1][j]表示考虑s[j]，不考虑s[i]; dp[i][j-1]表示考虑s[i]，不考虑s[j]

            根据递归方程中的i+1和j-1，可知遍历顺序为从下到上，从左到右

    1. #include 
    2. #include 
    3. #include 
    4.  
    5. class Solution {
    6. public:
    7.     int longestPalindromeSubseq(std::string s) {
    8.         // dp[i][j]表示在s[i, j]范围内的最长回文子串
    9.         std::vectorint>> dp(s.length(), std::vector<int>(s.length(), 0));
    10.         // 初始化
    11.         for(int i = 0; i < s.length(); i++) dp[i][i] = 1;
    12.         // 状态转移
    13.         // s[i] == s[j]时，dp[i][j] = dp[i+1][j-1] + 2
    14.         // s[i] != s[j]时，dp[i][j] = max(dp[i+1][j], dp[i][j-1]) 
    15.         // dp[i+1][j]表示考虑s[j]，不考虑s[i]; dp[i][j-1]表示考虑s[i]，不考虑s[j]
    16.         // 根据递归方程中的i+1和j-1，可知遍历顺序为从下到上，从左到右
    17.         for(int i = s.length() - 2; i >= 0; i--){
    18.             for(int j = i+1; j < s.length(); j++){
    19.                 if(s[i] == s[j]) dp[i][j] = dp[i+1][j-1] + 2;
    20.                 else{
    21.                     dp[i][j] = std::max(dp[i][j-1], dp[i+1][j]);
    22.                 }
    23.             }
    24.         }
    25.         return dp[0][s.length() - 1];
    26.     }
    27. };
    28.  
    29. int main(int argc, char* argv[]){
    30.     // s = "bbbab"
    31.     std::string test = "bbbab";
    32.     Solution S1;
    33.     int res = S1.longestPalindromeSubseq(test);
    34.     std::cout << res << std::endl;
    35. }

  • 相关阅读:
    【开源软件推荐】gorm 数据库反向生成status结构工具 gormt
    CleanMyMac X4.12.1苹果电脑系统优化软件更新功能介绍
    springboot线程池创建与使用
    dubbo学习（一）dubbo简介与原理
    vue和react的区别
    Linux基础知识
    二、线性代数
    超越datetime：Arrow，Python中的日期时间管理大师
    C++_跨平台编译_cmakefile中_添加内容
    【Visual Leak Detector】源码调试 VLD 库
  • 原文地址：https://blog.csdn.net/weixin_43863869/article/details/133132314