1.198.打家劫舍

力扣题目链接(opens new window)

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

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

class Solution { public: int rob(vector<int>& nums) { //dp[n]=max(dp[n-2]+x,dp[n-1]); vector<int> dp(nums.size()+1,0); dp[0]=0; dp[1]=nums[0]; for(int i=2;i<=nums.size();i++){ dp[i]=max(dp[i-2]+nums[i-1],dp[i-1]); } return dp[nums.size()]; } };

简单的递推公式

2.213.打家劫舍II

力扣题目链接(opens new window)

你是一个专业的小偷，计划偷窃沿街的房屋，每间房内都藏有一定的现金。这个地方所有的房屋都 围成一圈 ，这意味着第一个房屋和最后一个房屋是紧挨着的。同时，相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警 。

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

class Solution { public: //分情况讨论一下就可以了，不包含头或者不包含尾 int rob(vector<int>& nums) { if (nums.size() == 0) return 0; if (nums.size() == 1) return nums[0]; int result1 = robRange(nums, 0, nums.size() - 2); // 情况二 int result2 = robRange(nums, 1, nums.size() - 1); // 情况三 return max(result1, result2); } // 198.打家劫舍的逻辑 int robRange(vector<int>& nums, int start, int end) { if (end == start) return nums[start]; vector<int> dp(nums.size()); dp[start] = nums[start]; dp[start + 1] = max(nums[start], nums[start + 1]); for (int i = start + 2; i <= end; i++) { dp[i] = max(dp[i - 2] + nums[i], dp[i - 1]); } return dp[end]; } };

环形的情况，这里就需要进行分情况讨论，因为首尾不能同时被偷，所以这里分两个情况讨论，偷头部，或者偷尾部，计算两种情况得到的金额，取其中的最大值。

3.337.打家劫舍 III

力扣题目链接(opens new window)

在上次打劫完一条街道之后和一圈房屋后，小偷又发现了一个新的可行窃的地区。这个地区只有一个入口，我们称之为“根”。 除了“根”之外，每栋房子有且只有一个“父“房子与之相连。一番侦察之后，聪明的小偷意识到“这个地方的所有房屋的排列类似于一棵二叉树”。 如果两个直接相连的房子在同一天晚上被打劫，房屋将自动报警。

计算在不触动警报的情况下，小偷一晚能够盗取的最高金额。

class Solution { public: //树形dp，使用长度为2的数组记录当前节点的两种情况 //不偷当前节点的最大金额与偷当前节点的最大金额 int rob(TreeNode* root) { vector<int> result=robTree(root); return max(result[0],result[1]); } //使用后序遍历 //记录左右孩子节点的金额情况 //再计算当前节点的金额dp情况 vector<int> robTree(TreeNode* cur){ if(cur==nullptr){ return vector<int>{0,0}; } vector<int> left=robTree(cur->left); vector<int> right=robTree(cur->right); //偷当前节点 int val1=cur->val+left[0]+right[0]; //不偷当前节点 int val2=max(left[0],left[1])+max(right[0],right[1]); return {val2,val1}; } };

当前节点的金额有两种情况确定，偷左右孩子或者不偷左右孩子只偷当前节点。

树形dp，使用一个大小为2的数组来表示当前节点被偷与不被偷时的最大金额。

递归函数的目的是求出当前节点的最大金额，这里二叉树的遍历选择后序遍历，因为需要递归函数的返回值来进行下一步计算。

先计算左右孩子的最大金额，之后再计算当前节点的最大金额，当前节点的最大金额分两种情况，一种是偷当前节点，那么值就是当前节点的金额，以及左孩子返回数组中不偷左孩子的最大金额以及右孩子之和

另一种是不偷当前节点，那么值就是左孩子返回数组中偷左孩子节点的最大金额以及右孩子之和

最后返回两种情况的最大值。

4.121. 买卖股票的最佳时机

力扣题目链接(opens new window)

给定一个数组 prices ，它的第 i 个元素 prices[i] 表示一支给定股票第 i 天的价格。

你只能选择 某一天 买入这只股票，并选择在 未来的某一个不同的日子 卖出该股票。设计一个算法来计算你所能获取的最大利润。

返回你可以从这笔交易中获取的最大利润。如果你不能获取任何利润，返回 0 。

贪心做法

class Solution { public: int maxProfit(vector<int>& prices) { int low = INT_MAX; int result = 0; for (int i = 0; i < prices.size(); i++) { low = min(low, prices[i]); // 取最左最小价格 result = max(result, prices[i] - low); // 直接取最大区间利润 } return result; } };

因为只买卖一次所以记录左边最小值，与右边最大值即可，

动态规划做法

class Solution { public: int maxProfit(vector<int>& prices) { int len = prices.size(); if (len == 0) return 0; vector<vector<int>> dp(len, vector<int>(2)); dp[0][0] -= prices[0]; dp[0][1] = 0; for (int i = 1; i < len; i++) { dp[i][0] = max(dp[i - 1][0], -prices[i]); dp[i][1] = max(dp[i - 1][1], prices[i] + dp[i - 1][0]); } return dp[len - 1][1]; } };

这里是使用二维dp的做法，股票有两种状态，持有与不持有状态

dp[i][0]表示第i天持有状态的最大收益（前一天持有或者今天持有）

dp[i][1]表示第i天不持有状态的最大收益（前一天不持有或者今天卖出）

初始化，第1天时候持有即为负的当前价格，不持有即为0

之后遍历每天计算出每天不持有与持有的收益即可

最后返回最后一天不持有的值即可

5.122.买卖股票的最佳时机II

力扣题目链接(opens new window)

给定一个数组，它的第 i 个元素是一支给定股票第 i 天的价格。

设计一个算法来计算你所能获取的最大利润。你可以尽可能地完成更多的交易（多次买卖一支股票）。

注意：你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。

贪心做法

class Solution { public: int maxProfit(vector<int>& prices) { int result=0; for(int i=1;i<prices.size();i++){ result+=max(prices[i]-prices[i-1],0);//比前一天高就卖出 } return result; } };

只要比前一天高就直接卖出，因为可以多次买卖

动态规划做法

class Solution { public: int maxProfit(vector<int>& prices) { int len = prices.size(); vector<vector<int>> dp(len, vector<int>(2, 0)); dp[0][0] -= prices[0]; dp[0][1] = 0; for (int i = 1; i < len; i++) { dp[i][0] = max(dp[i - 1][0], dp[i - 1][1] - prices[i]); // 注意这里是和121. 买卖股票的最佳时机唯一不同的地方。 dp[i][1] = max(dp[i - 1][1], dp[i - 1][0] + prices[i]); } return dp[len - 1][1]; } };

因为可以买卖多次，所以第i天买入的时候要考虑前一天不持有股票时的利润

6.123.买卖股票的最佳时机III

力扣题目链接(opens new window)

给定一个数组，它的第 i 个元素是一支给定的股票在第 i 天的价格。

设计一个算法来计算你所能获取的最大利润。你最多可以完成 两笔 交易。

注意：你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。

class Solution { public: int maxProfit(vector<int>& prices) { //这里是使用了五种状态来记录当前的现金情况 //dp[i][j]表示第i天的第j个状态时现金最大值 //没有操作 （其实我们也可以不设置这个状态）与前一天不操作相同 //第一次持有股票，前一天第一次持有股票与今天第一次买股票之间的最大值 //第一次不持有股票，前一天第一次卖股票与今天第一次麦股票最大值 //第二次持有股票 //第二次不持有股票 if (prices.size() == 0) return 0; vector<vector<int>> dp(prices.size(), vector<int>(5, 0)); dp[0][1] = -prices[0]; dp[0][3] = -prices[0]; for (int i = 1; i < prices.size(); 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]); } return dp[prices.size() - 1][4]; } };

因为可以最多完成两笔交易，所以在每天的时候都会有五种状态

1.不操作，不买入也不卖出，值与前一天不操作的值相同

2.第一次持有股票状态（不是第一次买股票），前一天第一次持有股票状态与今天第一次买股票之间的最大值

3.第一次不持有股票状态（不是第一次卖股票），前一天第一次不持有股票与今天第一次卖股票之间的最大值

4.第二次持有股票状态

5.第二次不持有股票状态

之后需要初始化dp，第一天第一次持有股票状态与第二次持有股票状态的值都是当前股票价格的负数

然后遍历每天，计算出每天的五种状态值，最后返回最后一天第二次不持有股票状态的利润

7.188.买卖股票的最佳时机IV

力扣题目链接(opens new window)

给定一个整数数组 prices ，它的第 i 个元素 prices[i] 是一支给定的股票在第 i 天的价格。

设计一个算法来计算你所能获取的最大利润。你最多可以完成 k 笔交易。

注意：你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。

class Solution { public: //一样的，记录股票的状态 int maxProfit(int k, vector<int>& prices) { vector<vector<int>> dp(prices.size(),vector<int>(2*k+1,0)); for(int i=1;i<2*k;i+=2){ dp[0][i]=-prices[0]; } for(int i=1;i<prices.size();i++){ for(int j=0;j<2*k-1;j+=2){ dp[i][j+1]=max(dp[i-1][j+1],dp[i-1][j]-prices[i]); dp[i][j+2]=max(dp[i-1][j+2],dp[i-1][j+1]+prices[i]); } } return dp[prices.size()-1][2*k]; } };

一样的做法，都是记录每天股票的状态，这里可以买卖k次，说明一共有2*k+1个状态

之后进行初始化，第1天状态的索引是奇数的时候，值为第一天股票价格的负值

最后再遍历天数，当索引是奇数的时候说明买入，偶数的时候要卖出

8.309.最佳买卖股票时机含冷冻期

力扣题目链接(opens new window)

给定一个整数数组，其中第 i 个元素代表了第 i 天的股票价格 。

设计一个算法计算出最大利润。在满足以下约束条件下，你可以尽可能地完成更多的交易（多次买卖一支股票）:

• 你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。
• 卖出股票后，你无法在第二天买入股票 (即冷冻期为 1 天)。

class Solution { public: /* 状态一：持有股票状态,前一天已经持有或者前一天冷冻期今天买入或者前一天保持卖出股票的状态今天买入 状态二：保持卖出股票的状态，前一天为冷冻期或者前一天也是保持卖出股票状态 状态三：今天卖出股票，前一天是持有股票状态 状态四：今天为冷冻期状态，前一天一定是卖出股票 */ int maxProfit(vector<int>& prices) { vector<vector<int>> dp(prices.size(),vector<int>(4,0)); dp[0][0]=-prices[0]; for(int i=1;i<prices.size();i++){ dp[i][0]=max(dp[i-1][0],max(dp[i-1][3]-prices[i],dp[i-1][1]-prices[i])); dp[i][1]=max(dp[i-1][3],dp[i-1][1]); dp[i][2]=dp[i-1][0]+prices[i]; dp[i][3]=dp[i-1][2]; } return max(dp[prices.size()-1][1],max(dp[prices.size()-1][2],dp[prices.size()-1][3])); } };

这里由于存在冷冻期，所以一共可以分为四种状态

1.持有股票状态，前一天持有股票或者今天买入股票（前一天冷冻期）或者今天买入股票（前一天不持有股票）

2.不持有股票的状态，前一天不持有股票（前一天冷冻期或者前一天也不持有股票）

3.今天卖出股票状态，前一天持有股票

4.今天为冷冻期状态，前一天卖出股票

之后遍历天数计算出每天的状态值

最后返回的是三种状态中的最大值，不持有状态，与冷却期状态，与最后一天卖出股票状态

9.714.买卖股票的最佳时机含手续费

力扣题目链接(opens new window)

给定一个整数数组 prices，其中第 i 个元素代表了第 i 天的股票价格 ；非负整数 fee 代表了交易股票的手续费用。

你可以无限次地完成交易，但是你每笔交易都需要付手续费。如果你已经购买了一个股票，在卖出它之前你就不能再继续购买股票了。

返回获得利润的最大值。

注意：这里的一笔交易指买入持有并卖出股票的整个过程，每笔交易你只需要为支付一次手续费

class Solution { public: int maxProfit(vector<int>& prices, int fee) { int n=prices.size(); //两个状态，有股票与没有股票 //dp[i][0] 表示第i天有股票时的余额 //dp[i][1] 表示第i天没有股票的余额 vector<vector<int>> dp(prices.size(),vector<int>(2,0)); dp[0][0]=-prices[0]; for(int i=1;i<prices.size();i++){ //i天有股票表示前一天有股票或者前一天没股票今天卖股票 dp[i][0]=max(dp[i-1][0],dp[i-1][1]-prices[i]); //i天没有股票表示前一天有股票或者前一天有股票扣除手续费 dp[i][1]=max(dp[i-1][1],dp[i-1][0]+prices[i]-fee);//扣除手续费 } return dp[n-1][1]; } };

这里与买卖股票最佳时机2是类似的，不过在卖出股票的时候要多扣除手续费

股票问题总结

根据股票买卖的次数可以分类

总而言之就是分析出每天的股票可以有几种状态，根据不同的状态推断出不同的递推公式，之后遍历天数，填充dp二维数组，最后返回最后一天的最大值。