返回获得利润的最大值

发布时间：2025-06-24 04:30:56  作者：北方职教升学中心  阅读量：305

g要用到 g的i-1，f的 i-1，j-1。
i - 1 天结束处于买入状态，i天先要把股票卖了i天结束之后处于冷冻期，才能进入可交易。

classSolution{public:intmaxProfit(intk,vector<int>&prices){//处理细节问题intn =prices.size();k =min(k,n /2);// 1.创建 dp 表// 2.初始化// 3.填表// 4.返回值constintINF =0x3f3f3f3f;vector<vector<int>>f(n,vector<int>(k +1,-INF));autog =f;f[0][0]=-prices[0],g[0][0]=0;for(inti =1;i <n;++i){for(intj =0;j <k +1;++j){f[i][j]=max(f[i -1][j],g[i -1][j]-prices[i]);g[i][j]=g[i -1][j];if(j >=1)//如果状态存在g[i][j]=max(g[i][j],f[i -1][j -1]+prices[i]);}}intret =0;for(auto&e :g[n -1])ret =max(ret,e);returnret;}};

所以我们可以先用数组arr，把这些数先统计一下。之后，你必须删除 所有 等于 nums[i] - 1 和 nums[i] + 1 的元素。
碰到这种情况其实有一种技巧，通过修改状态转移方程
g[i][j]，当 j = 0的时候，f[i-1][j-1] j - 1会越界，表示在 i - 1 天完成了 -1 笔交易，这种状态根本不存在，所以可以修改状态转移方程，满足的情况的时候在比较。涂到 i - 1 位置只能涂成蓝色、

算法原理：

1.状态表示

经验 + 题目要求

dp[i] 表示：选择到 i 位置的时候，此时最长预约时长。
i - 1 天结束处于买入状态，i 天卖掉股票，i天之后就处于冷冻期了。也就是说今天是交易2次的话，我要找到昨天交易1次的次数买入，今天卖掉交易次数不就是变成2次了， 所以是 j - 1）+ p[i])

3.初始化

f 要用到 f的 i-1，g的 i-1，因此要初始化 f 第一行 和 g 第一行。这个数的好处在于足够小。所以第 0 天的时候，完成一笔交易、

在 i 天结束处于冷冻期状态，看 i - 1 天是什么状态然后满足 i 天结束处于冷冻期

i - 1 天结束处于冷冻期不能 i 天也处于冷冻期，不能卖了还卖只有一支股票。
如果 i - 1 天结束处于可交易状态，只要把 i 天 股票买了就进入买入状态。

但是 i 位置可以选或者不选，因此继续细化

f[i] 表示：选择到 i 位置的时候，nums[i] 必选，此时最长预约时长

g[i] 表示：选择到 i 位置的时候，nums[i] 不选，此时最长预约时长

2.状态转移方程

f[i] 表示 必选 i 位置，此时最长预约时长。i 位置可以选，那 i - 1 位置就不能选了，而我们想要的是最长预约时长，那就把 0 ~ i- 1 区间内最长预约时长给我，这个最长预约时长保证 i - 1 位置必不选。然后状态转移方程就可以根据这个图直接得到。绿色，dp[i-1][1]表示涂到 i - 1 位置涂蓝色此时最小花费，dp[i-1][2]表示涂到 i - 1 位置涂绿色此时最小花费，因此 i 位置涂成红色状态转移方程就处理了，剩下也是这样的处理：

3.初始化

填表时不越界

这里我们可以多申请一个空间。继续细分：

i 天结束之后，此时处于 " 买入" 状态

i 天结束之后，此时处于 " 可交易（卖出后手里没有股票了并且此时不处于冷冻期）" 状态

i 天结束之后，此时处于 " 冷冻期 " 状态

dp[i][0] 表示： 第 i 天结束之后，处于 " 买入 " 状态，此时的最大利润
dp[i][1] 表示： 第 i 天结束之后，处于 " 可交易 " 状态，此时的最大利润
dp[i][2] 表示： 第 i 天结束之后，处于 " 冷冻期" 状态，此时的最大利润

2.状态转移方程

此时分三种情况讨论：

可以画一个状态机，看自己能不能到自己，自己能不能到其他。

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

f[0] 表示第 0 天结束之后，处于 “买入” 状态，那就把股票买了就行了，
f[0] = -p[0]

g[0] 表示第 0 天结束之后，处于 “卖出” 状态，卖出手里得有股票啊但是并没有，那第 0 天啥也不干不，不还是处于卖出状态吗
g[0] = 0

4.填表

从左往右，两个表一起填

5.返回值

如果最后一天处于买入状态，你能获得最大利润吗？肯定不如最后一天卖入状态！

返回 g[n-1]

classSolution{public:intmaxProfit(vector<int>&prices,intfee){// 1. 创建 dp 表// 2. 初始化// 3. 填表// 4. 返回值intn =prices.size();vector<int>f(n);vector<int>g(n);f[0]=-prices[0];for(inti =1;i <n;++i){f[i]=max(f[i -1],g[i -1]-prices[i]);g[i]=max(g[i -1],f[i -1]+prices[i]-fee);}returng[n-1];}};

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

题目链接：123. 买卖股票的最佳时机 III

题目分析：

这道题还是买卖股票求最大利润，但是和前面无限次交易相比，你最多可以完成 两笔交易。

4.填表顺序

从上到下填写每一行，每一行从左往右，两个表一起填

5.返回值

最大利润可能是交易0次、
总结来说 f 要初始化第一行第一列，g 初始化第一行。

i - 1 天结束处于卖出状态，i 天啥也不干，i 天结束之后也处于卖出状态
i - 1 天结束处于买入状态，i 天把股票卖掉，i 天结束之后处于卖出状态

别忘记买卖股票是有手续费的，这里我们在卖出股票交手续费。

所以不仅要有买入、完成 2 笔交易 此时处于 买入 状态。
i - 1 天结束处于冷冻期，i 天啥也不干，就进入i天结束处于可交易

3.初始化

填表时不越界

dp[0][0] (买入状态) = -p[0]
dp[0][1] (可交易) = 0
dp[0][2] (冷冻状态) = 0

4.填表

从左往右三个表一起填

5.返回值

返回最后一个位置最大利润，i 天 还买股票肯定是不行的。 i 位置不选，那 i - 1 位置可选可不选，我们要找的是 0 ~ i - 1区间最长预约时长，有两种情况，选 i - 1 位置 ，而 f[i - 1] 表示必选 i - 1 位置此时最长预约时长， 不选 i - 1 位置，g[i - 1] 表示 不选 i - 1 位置此时最长预约时长

3.初始化

填表时不越界

这里我们也可以添加虚拟节点，但是这道题初始化太简单了，因此就不要添加虚拟节点。完成 1 笔交易 此时处于 买入 状态、

开始你拥有 0 个点数。

f[i][j] 表示： 第 i 天结束之后，完成了 j 次交易，此时处于 “买入” 状态下的，最大利润

g[i][j] 表示： 第 i 天结束之后，完成了 j 次交易，此时处于 “卖入” 状态下的，最大利润

2.状态转移方程

如果有多个状态并且多个状态之间还能相互转化，建议画个状态机。

所以如果说，数组是有序的话并且中间没有间隔，就是 “打家劫舍” 问题。

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

算法原理：

1.状态表示

经验 + 题目要求

dp[i] 表示 第 i 天结束之后，此时最大利润。因此我们定义两个二维数组，
i 表示天数，j表示交易次数。这样就可以把所有情况不重不漏的找出来。如果中间数断了，就不是 “打家劫舍” 问题。

f[0][0]表示： 第 0 天结束之后，完成了 0 次交易，此时处于 “买入” 状态下的，是不是把第 0 天股票买了才行 ，所以 f[0][0] = -p[0]

g[0][0] 表示： 第 0 天结束之后，完成了 0 次交易，此时处于 “卖入” 状态下的，卖出是手里没有股票的状态，那第 0 天我什么都不敢不就好了，所以g[0][0] = 0

但是这里有个细节：

如果你选的是 INI_MIN 去初始化，这里发生减操作，INI_MIN - 1 绝对会越界！！！超出int的范围。

4.填表

从左往右三个表一起填

5.返回值

返回涂到最后一个位置，涂成红，蓝，绿最小花费

min（dp[n][0]，dp[n][1]，dp[n][2]）

classSolution{public:intminCost(vector<vector<int>>&costs){// 1. 创建 dp 表// 2. 初始化// 3. 填表// 4. 返回值intn =costs.size();vector<vector<int>>dp(n +1,vector<int>(3));for(inti =1;i <=n;++i){dp[i][0]=min(dp[i -1][1],dp[i -1][2])+costs[i -1][0];dp[i][1]=min(dp[i -1][0],dp[i -1][2])+costs[i -1][1];dp[i][2]=min(dp[i -1][0],dp[i -1][1])+costs[i -1][2];}returnmin(dp[n][0],min(dp[n][1],dp[n][2]));}};

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

题目链接：309. 买卖股票的最佳时机含冷冻期

题目分析：

卖出股票后，你无法在第二天买入股票 (即冷冻期为 1 天)。所以初始化只用初始化第一行就可以了。

为什么这样初始化，分析f表发现初始f和g表第一行就可以，分析g表发现某个位置会影响初始化，所以就把这个位置单独处理。
这里填f[0] 和 g[0] 会越界。

对于删除它并获得 nums[i] 的点数。

上面意思是，买卖一次股票，要支付手续费，要不就是买支付要么就是卖支付，只用支付一次。

然后就可以不要nums了，相当于在arr数组做一次 “打家劫舍” 。但第 i 天结束之后可以细化为两种状态：

f[i] 表示：第 i 天结束之后，处于 “买入” 状态，此时的最大利润
g[i] 表示：第 i 天结束之后，处于 “卖入” 状态，此时的最大利润

我们可以搞两个dp表或者开一个dp(2*n)表

2.状态转移方程

如果是多状态，并且多状态之间可以相互转移，为了可以不重不漏的把所有情况都考虑到，建议画一个状态机，先看自己能不能到自己，在看其他的能不能到自己。

如果 i - 1 天结束处于买入状态，那 i 天啥也不干，依旧处于 买入状态。3、每个房子粉刷成不同颜色的价格由一个3*n的矩阵给出，左边0 ~ 2表示房子，上面0 ~ 2表示每个房子被粉刷不能颜色的价格。

预处理：将数组中的数，统计到 arr 中，然后在 arr 中，做一次 “打家劫舍” 问题即可

1.状态表示

经验 + 题目要求

f[i] 表示：选到 i 位置的时候， nums[i] 必选 ，此时能获得的最大点数

g[i] 表示：偷到 i 位置的时候，nums[i] 不选，此时能获得的最大点数

2.状态转移方程

3.初始化

填表时不越界

f[0] = arr[0] ，g[0] = 0

4.填表

从左往右两个表一起填

5.返回值

返回偷到最后一个位置时最大金额

max( f[n - 1]，g[n - 1] )

classSolution{public:intdeleteAndEarn(vector<int>&nums){// 1. 预处理constintn =10001;intarr[n]={0};for(autoe :nums){arr[e]+=e;}// 2.在 arr 数组上，做一次 "打家劫舍" 问题// 1. 创建 dp 表// 2. 初始化// 3. 填表// 4. 返回值vector<int>f(n);vector<int>g(n);//这道题可以不用初始化for(inti =1;i <n ;++i){f[i]=g[i -1]+arr[i];g[i]=max(f[i -1],g[i -1]);}returnmax(f[n -1],g[n -1]);}};

4.粉刷房子

题目链接：LCR 091. 粉刷房子

题目分析：

有n个房子，每个房子都可以被粉刷成红色，蓝色，绿色，相邻的房子颜色不能相同。卖出状态还要加上交易次数。返回你能通过这些操作获得的最大点数。这样就可以把初始化放到填表里面了。并且在这个数上做加减操作不会越界！

求最小值，不要选 INI_MAX，选择 -0x3f3f3f3f去初始化。我们处理一下。
i - 1 天结束处于可交易，手里没有股票可以卖，不能到冷冻期

在 i 天结束处于可交易状态，看 i - 1 天是什么状态然后满足 i 天结束处于可交易

i - 1 天结束处于可交易，i 天啥也不干，还是可交易状态。 选 1 之后不能选 2 了，是不是就是不能选择相邻的两个数并且要最终选择的数最大。

同时，相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警 。1次、

算法原理：

1.状态表示

经验 + 题目要求

dp[i] 表示 第 i 天结束之后，此时最大利润。

classSolution{public:intmaxProfit(vector<int>&prices){// 1.创建 dp 表// 2.初始化// 3.填表// 4.返回值constintINF =0x3f3f3f3f;intn =prices.size();vector<vector<int>>f(n,vector<int>(3,-INF));autog =f;f[0][0]=-prices[0];g[0][0]=0;for(inti =1;i <n;++i){for(intj =0;j <3;++j){f[i][j]=max(f[i-1][j],g[i-1][j]-prices[i]);g[i][j]=g[i-1][j];if(j -1>=0)//如果该状态存在g[i][j]=max(g[i][j],f[i-1][j-1]+prices[i]);}}//找到最后一行最大值intret =0;for(auto&e :g[n-1]){ret =max(e,ret);}returnret;}};

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

题目链接：188. 买卖股票的最佳时机 IV

题目分析：

这道题和上面的题几乎完全一模一样，上面最多只能进行两笔交易，而这道题最多能完成 k 笔交易。

i 天结束之后处于买入状态，就看 i - 1 天结束的状态。比如说选了下标1里面的数，那下标 2 里面的数就不能要了，也就相当于选择当前这个数，相邻的数不能选了。

算法原理：

1.状态表示

经验 + 题目要求

以 i 位置为结尾，当涂到 i 位置的时候此时的最小花费，但是涂到 i 位置还可以细分，涂成红色，蓝色，绿色。

max（dp[n-1][1]，dp[n-1][2]）

classSolution{public:intmaxProfit(vector<int>&prices){// 1.创建 dp 表// 2.初始化// 3.填表// 4.返回值intn =prices.size();vector<vector<int>>dp(n,vector<int>(3));dp[0][0]=-prices[0];for(inti =1;i <n;++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][2]);dp[i][2]=dp[i-1][0]+prices[i];}returnmax(dp[n-1][1],dp[n-1][2]);}};

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

题目链接：714. 买卖股票的最佳时机含手续费v

题目分析：

给定一个整数数组 prices，其中 prices[i]表示第 i 天的股票价格 ；整数 fee 代表了交易股票的手续费用。可以选后面其他的数。

因为我们交易次数是有限制的，所以要珍惜交易次数，尽量不要当天买了之后又卖。

这里的「处于冷冻期」指的是在第 i 天结束之后的状态。

这条线的起点表示 i - 1 天结束之后的状态，线表示 i 天的操作，箭头所指的是当天结束之后的状态。两笔交易是不存在的，并且因为我们求得是max不想它们干扰后面的结果，所以我们可以给第 0 天给买和卖 第一笔交易、

i 天结束之后处于买入状态：

i - 1 天结束之后也处于买入状态，i 天啥也不干， i 天结束之后还是处于买入状态
i - 1 天结束之后处于卖出状态，i 天买入当天股票，i 天结束之后处于买入状态

i 天结束之后处于卖出状态:

i - 1 天结束之后处于卖出状态，i 天啥也不干，i 天结束之后还是处于卖出状态
i -1 天结束之后处于买入状态，i 天卖出股票，i 天结束之后处于卖出状态

但是这道题要注意，这道题要把交易次数加上，在转化的过程那一步会改变交易的次数呢？
前一天买了股票，如果今天把股票给卖了之后，在今天结束之后，是不是相当于完成了一笔交易，然后交易次数+1。2、

比如在 i 天结束处于买入状态，看 i - 1 天是什么状态然后满足 i 天结束处于买入状态。2次，所以返回g表的最后一行里面的最大值。要找到粉刷完所有房子最少的价格。

此时状态转移方程就出来了：

f[i][j] = max（f[i-1][j]（前一天处于买入状态，今天啥也不干，交易次数不变），g[i-1][j]（前一天处于卖出状态， 今天只是买股票，并没有卖，没有完成交易，因此交易次数不变）- p[i]）

g[i][j] = max(g[i-1][j]（前一天完成了一笔交易，但是今天啥也不干，交易次数不变），f[i-1][j-1]（第 i 天结束之后 j 的交易次数要 + 1，我要找到昨天的交易次数那是不是 j 要 -1。

因为我们多开一个空间，相当于整体向右移一位，如果要回去应该 下标应该减 1。删除 所有 等于 nums[i] - 1 和 nums[i] + 1 的元素也就是说值等于这两个的数不能选了。

i - 1 天结束处于买入状态，i 天啥也不干，也处于买入状态
i - 1 天结束处于卖出状态，i 天把股票买了，i 天结束处于买入状态

i 天结束之后处于卖出状态，就看 i - 1 天结束的状态。比如说1、

但是这里的数并不是那么连续的。

算法原理：

分类讨论：

根据第一个位置选or不选可以把问题从环形问题转化为线性问题

接下来是打家劫舍I的分析，和上面那道题几乎一模一样

1.状态表示

经验 + 题目要求

f[i] 表示：偷到 i 位置的时候，偷 nums[i] ，此时的最大金额

g[i] 表示：偷到 i 位置的时候，不偷 nums[i] ，此时的最大金额

2.状态转移方程

3.初始化

填表时不越界

f[0] = nums[0] ，g[0] = 0

4.填表

从左往右两个表一起填

5.返回值

返回偷到最后一个位置时最大金额

max( f[n - 1]，g[n - 1] )

classSolution{public:introb(vector<int>&nums){intn =nums.size();//分类讨论两种情况下最大值returnmax(dp(nums,2,n-2)+nums[0],dp(nums,1,n -1));}intdp(vector<int>&nums,intleft,intright){if(left >right)return0;// 1.创建 dp 表// 2.初始化// 3.填表// 4.返回值intn =nums.size();vector<int>f(n);vector<int>g(n);f[left]=nums[left],g[left]=0;for(inti =left +1;i <=right;++i){f[i]=g[i -1]+nums[i];g[i]=max(f[i -1],g[i -1]);}returnmax(f[right],g[right]);}};

3.删除并获得点数

题目链接：740. 删除并获得点数

题目分析：

给你一个整数数组 nums ，你可以对它进行一些操作。为什么预处理到数组中，因为 下标 i 是有序的。

算法原理：

1.状态表示

经验 + 题目要求

dp[i] 表示 第 i 天结束之后，所获得得最大利润，但是股票问题在第 i 天结束之后可以划分很多子状态，比如第 i 天结束手里有股票或者没有股票，此时就可以分为"卖入" 和 “卖出” 状态，而且这道题更为特殊最多只能完成两笔交易，所以我们可以有更多子状态：

第 i 天结束 ，完成 0 笔交易 此时处于 买入 状态、填f[0]，g[0] 会越界，而f[0]表示必选0位置，g[0]表示不选0位置，因此

f[0] = nums[0] ，g[0] = 0

4.填表

从左往右两个表一起填

5.返回值

返回到达最后一个位置时最长预约时长

max( f[n - 1]，g[n - 1] )

classSolution{public:intmassage(vector<int>&nums){// 1.创建dp表// 2.初始化// 3.填表// 4.返回值intn =nums.size();if(n ==0)return0;//处理边界情况vector<int>fdp(n);vector<int>gdp(n);fdp[0]=nums[0],gdp[0]=0;for(inti =1;i <n;++i){fdp[i]=gdp[i -1]+nums[i];gdp[i]=max(fdp[i -1],gdp[i -1]);}returnmax(fdp[n -1],gdp[n -1]);}};

2.打家劫舍 II

题目链接：213. 打家劫舍 II

题目分析：

这道题相比于打家劫舍I 多了这个条件：这个地方所有的房屋都 围成一圈，这意味着第一个房屋和最后一个房屋是紧挨着的，也就是说现在成了一个环路了。之后，你必须删除 所有 等于 nums[i] - 1 和 nums[i] + 1 的元素。并且手里只能有一支股票，卖出去之前不能再次买入。因此：

如果是求最大值不要选 INI_MIN，选择- 0x3f3f3f3f去初始化，（0x3f3f3f3f是是int最大值的一半）。你可以无限次完成交易，返回获得利润的最大值。

算法原理：

一定要有这样的能力，碰到一个新题的时候，可以往之前做过的题方向靠！

比如这道题如果是有序的并且中间数没有少，就像打家劫舍的问题。也就是小于等于k笔交易都行

算法原理：

和上面几乎一模一样，不过可以这里可以处理一个细节问题，可以提高时间复杂度和空间复杂度

如果给了 20 天 ， k = 30，可以进行30笔交易。

你可以无限次地完成交易，但是你每笔交易都需要付手续费。下标 i 表示这个数是几，arr[i] 表示 " i " 这个数出现的总和。而 g[i-1] 表示 i -1位置不选此时最长预约时长。

状态转移方程就出来了

3.初始化

可以申请虚拟节点，但是没必要。当然也别忘记 i 位置的预约时长

g[i] 表示 不选 i 位置，此时最长预约时长。

第 i 结束，完成 0 笔交易 此时处于 卖出 状态，完成 1 笔交易 此时处于 卖出 状态，完成 2 笔交易 此时处于 卖出 状态。也就是说只能买卖两次！并且手里股票卖了之后才能在买股票。5。