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

系统管理员 2024-04-27 06:51 7阅读 0赞

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

#### 目录 ####

*  一、AcWing1049. 大盗阿福
 *   *  题目解析
     *  解题代码
 *  二、AcWing1058. 股票买卖 V
 *   *  题目解析
     *  解题代码
 *  三、AcWing1059. 股票买卖 VI
 *   *  题目解析
     *  解题代码

## 一、AcWing1049. 大盗阿福 ##

**原题链接：[点击直接跳转到该题目][Link 3]**

### 题目解析 ###

**我们本题用到了两个一维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 ##

**原题链接：[点击直接跳转到该题目][Link 4]**

### 题目解析 ###

**状态表示（`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 item
    
    const 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 ##

**原题链接：[点击直接跳转到该题目][Link 5]**

### 题目解析 ###

**`状态表示`：`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;
    }

[Link 1]: https://xiaofeizhu.blog.csdn.net/
[Link 2]: https://blog.csdn.net/m0_74352571/category_12364106.html
[AcWing]: https://blog.csdn.net/m0_74352571/category_12481646.html?spm=1001.2014.3001.5482
[Link 3]: https://www.acwing.com/problem/content/1051/
[Link 4]: https://www.acwing.com/problem/content/1060/
[Link 5]: https://www.acwing.com/problem/content/1061/