【算法|动态规划 | 线性dp | 状态机模型】AcWing1049. 大盗阿福 1058. 股票买卖 V AcWing1059. 股票买卖 VI

本文主要是介绍【算法|动态规划 | 线性dp | 状态机模型】AcWing1049. 大盗阿福 1058. 股票买卖 V AcWing1059. 股票买卖 VI，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

个人主页：兜里有颗棉花糖
欢迎点赞👍 收藏✨ 留言✉ 加关注💓本文由兜里有颗棉花糖原创
收录于专栏【手撕算法系列专栏】【AcWing算法提高学习专栏】
🍔本专栏旨在提高自己算法能力的同时，记录一下自己的学习过程，希望对大家有所帮助
🍓希望我们一起努力、成长，共同进步。

一、AcWing1049. 大盗阿福

原题链接：点击直接跳转到该题目

题目解析

我们本题用到了两个一维dp表分别是f[i]、g[i]

状态表示：

f[i]：表示偷窃第i家所能窃取的最大值
g[i]：表示不偷窃第i家所能窃取的最大值

状态转移方程：

f[i] = max(g[i - 1] + arr[i])
g[i] = max(f[i - 1],g[i - 1])

返回值：

max(f[n],g[n])

解题代码

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;const int N  = 1e5 + 10;int main()
{int T;cin >> T;while(T--){int f[N],g[N],arr[N];int n;cin >> n;for(int i = 1;i <= n;i++) cin >> arr[i];// dp初始化f[1] = arr[1];for(int i = 1;i <= n;i++){f[i] = g[i - 1] + arr[i];g[i] = max(f[i - 1],g[i - 1]);}cout << max(f[n],g[n]) << endl;}
}

二、AcWing1058. 股票买卖 V

原题链接：点击直接跳转到该题目

题目解析

状态表示（dp[0/1/2][i]）：

0表示第i天结束后处于卖出状态，即手上没有股票
1表示第i天结束后处于买入状态，即手上右股票
2表示第i天结束后处于冷冻期（我们这里就可以理解为此时的第i天这一整天是处于冷冻期的）

返回值（结果值）：

dp[0][n]

解题代码

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;- List itemconst int N = 1e5 + 10;
int prices[N];
int dp[3][N]; // 0表示卖出状态，1表示买入状态，2表示冷冻期int main()
{int n;cin >> n;for(int i = 1;i <= n;i++) cin >> prices[i];// dp初始化dp[1][1] = -prices[1];for(int i = 2;i <= n;i++) {dp[0][i] = max(dp[0][i - 1],dp[1][i - 1] + prices[i]);dp[1][i] = max(dp[1][i - 1],dp[2][i - 1] - prices[i]);dp[2][i] = dp[0][i - 1];}printf("%d\n",dp[0][n]);return 0;
}

三、AcWing1059. 股票买卖 VI

原题链接：点击直接跳转到该题目

题目解析

状态表示：dp[0/1][i]，0表示第i天结束后没有手上没有股票；1表示第i天结束后手上有股票。

dp[0][i]：表示第i天结束后手上没有股票的最大利益。
dp[1][i]：表示第i天结束后手上有股票的最大利益。

状态转移方程：

dp[0][i] = max(dp[0][i - 1],dp[1][i - 1]) + prices[i] - f
dp[1][i] = max(dp[1][i - 1],dp[0][i - 1] - prices[i])

返回值（即最终结果值）：

由于最终手中一定是没有股票的，所以最后的结果值为dp[0][n]

解题代码

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;const int N = 1e5 + 10;
int prices[N];
int dp[2][N];int main()
{int n,f;scanf("%d %d",&n,&f);for(int i = 1;i <= n;i++) cin >> prices[i];dp[1][1] = -prices[1];for(int i = 2;i <= n;i++){dp[0][i] = max(dp[0][i - 1],dp[1][i - 1] + prices[i] - f);dp[1][i] = max(dp[1][i - 1],dp[0][i - 1] - prices[i]);}printf("%d\n",dp[0][n]);return 0;
}