【动态规划】简单多状态

旧城等待， 2024-03-22 21:14 78阅读 0赞

#### 文章目录 ####

*  动态规划（简单多状态）
 *   *  1. 按摩师
     *  2. 打家劫舍 ||
     *  3. 删除并获得点数
     *  4. 粉刷房子
     *  5. 最佳买卖股票时机含冷冻期
     *  6. 买卖股票的最佳时机含手续费
     *  7. 买卖股票的最佳时机 |||
     *  8. 买卖股票的最佳时机 IV

## 动态规划（简单多状态） ##

### 1. 按摩师 ###

[题目链接][Link 1]

1.  状态表示
    
    `dp[i]`表示到i位置的时候预约的最大时长。但是这个题目我们可以选择接或不接。因此可以继续划分为两个子状态：
    
     *  `f[i]`表示：到i位置时接受的最大时长
     *  `g[i]`表示：到i位置时不接受的最大时长
2.  状态转移方程
    
    ![2vu4cjw7da-1690362953455.png][]
3.  初始化
    
    因为这个题目比较简单，所以不需要使用虚拟节点的方法，初始化是为了后面填表的时候不越界
    
    `f[0] = nums[0], g[0] = 0`
4.  填表
    
    从左到右
5.  返回值
    
    接受最后一个或者不接受的最大值

AC代码：

class Solution 
    {
        
    public:
        int massage(vector<int>& nums) 
        {
        
            int n = nums.size();
            if (n == 0) return 0;
            vector<int> f(n);
            auto g = f;
            f[0] = nums[0], g[0] = 0;
            for (int i = 1; i < n; i++)
            {
        
                f[i] = g[i - 1] + nums[i];
                g[i] = max(f[i - 1], g[i - 1]);
            }
            return max(f[n - 1], g[n - 1]);
        }
    };

### 2. 打家劫舍 || ###

[题目链接][Link 2]

分析：

由于房间是连续的，也就是一个环，因此可以分类讨论：

*  偷第一个时，第二个和最后一个不能偷
 *  不偷第一个，可以偷第二个和最后一个

因此只需要两种情况的最大值就可以

1.  状态表示
    
    `dp[i]`表示偷到i时的最大金额，但是依然可以划分为两种情况偷或不偷
    
    `f[i]`表示偷i时的最大金额
    
    `g[i]`表示不偷i时的最大金额
2.  状态转移方程
    
    ![qx81yjpg3g-1690364303443.png][]
3.  初始化
    
    保证后续的填表不越界
4.  填表
    
    从左到右，两个一起填
5.  返回值
    
    最大值

AC代码：

class Solution 
    {
        
    public:
        int rob(vector<int>& nums) 
        {
        
            int x = 0, y = 0;
            int n = nums.size();
            x += nums[0];
            x += recursion(2, n - 2, nums);
            y += recursion(1, n - 1, nums);
            return max(x, y);
        }
        int recursion(int left, int right, vector<int> &v)
        {
        
            if (left > right) return 0;
            int n = v.size();
            vector<int> f(n);
            auto g = f;
            f[left] = v[left]; // 初始化
            for (int i = left + 1; i <= right; i++)
            {
        
                f[i] = g[i - 1] + v[i];
                g[i] = max(g[i - 1], f[i - 1]);
            }
            return max(f[right], g[right]);
        }
    };

### 3. 删除并获得点数 ###

[题目链接][Link 3]

分析：我们把所有数字的点数之和，放到一个数组当中，在进行一次打家劫舍就可以了

把原数组转换成一个新数组，新数组的下标`i`所对应的值为原数组的元素`i`在原数组中数字的总和，比如原数组`[2, 2, 3, 3, 3, 4]`,转换为新数组就是`[0, 0, 4, 9, 4]`。在新数组中，下标`0和1`表示在原数组中没有`0和1`这两个数，新数组下标`2`的值是`4`，表示在原数组中，所有`2`的总和是`4`。转换的目的就是可以从新数组中得到删除`nums[i]`而得到的点数，也就是可以打劫的金额。因为删除`nums[i]`后，还要删除`nums[i] + 1`和`nums[i] - 1`，在新数组中就意味着不能取相邻的元素，不能取相邻的元素和打家劫舍也是一样的。接下来就可以使用打家劫舍的方式解答了

AC代码：

class Solution 
    {
        
    public:
        const int N = 10001;
        int deleteAndEarn(vector<int>& nums) 
        {
        
            vector<int> arr(N);
            for (auto e : nums) arr[e] += e;
            vector<int> g(N);
            auto f = g;
            for (int i = 1; i < N; i++)
            {
        
                f[i] = g[i - 1] + arr[i];
                g[i] = max(g[i - 1], f[i - 1]);
            }
            return max(g[N - 1], f[N - 1]);
        }
    };

### 4. 粉刷房子 ###

[题目链接][Link 4]

1.  状态表示
    
    `dp[i]`表示到i时，所需的最少费用。但是到i的时候可以有三种情况我们需要分三个子状态
    
    `dp[i][0], dp[i][1], dp[i][2]`
2.  状态转移方程
    
    ![wrmwgl7sbc-1690365960472.png][]
3.  初始化
    
    采用虚拟节点的方式
4.  填表
5.  返回值
    
    返回三个表中的最小值

AC代码：

class Solution 
    {
        
    public:
        int minCost(vector<vector<int>>& costs) 
        {
        
            // 0: 红色 1：蓝色 2：绿色
            int n = costs.size();
            vector<vector<int>> dp(n + 1, vector<int>(3));
            for (int i = 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];
            }
            int ret = INT_MAX;
            for (int i = 0; i < 3; i++)
            {
        
                ret = min(ret, dp[n][i]);
            }
            return ret;
        }
    };

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

[题目链接][Link 5]

1.  状态表示
    
    `dp[i]`表示到i位置时的最大利润，但是到达i位置的时候仍然有3种子状态
    
     *  `dp[i][0]`，表示i过后处于买入状态
     *  `dp[i][1]`， 表示i过后处于可交易状态
     *  `dp[i][2]`，表示i过后处于冷冻期状态
2.  状态转移方程
    
    像这种状态之间可以相互转换的，我们可以采用如下方法分析：
    
    ![bh40p1zbcb-1690367957450.png][]
3.  初始化
    
    `dp[0][0] = -prices[0], dp[0][1] = 0, dp[0][2] = 0`
4.  填表
    
    三张表同时填
5.  返回值
    
    返回三中状态最后的最大值

AC代码：

class Solution 
    {
        
    public:
        int maxProfit(vector<int>& prices) 
        {
        
            int n = prices.size();
            vector<vector<int>> dp(n, vector<int>(3));
            dp[0][0] = -prices[0];
            for (int i = 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];
            }
            return max(max(dp[n - 1][0], dp[n - 1][1]), dp[n - 1][2]);
        }
    };

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

[题目链接][Link 6]

1.  状态表示
    
    `dp[i]`表示到i位置的时候，最大的利润但是到i位置的时候是有两种状态的
    
    `dp[i][0]`：表示是买入状态
    
    `dp[i][1]`表示卖出状态
2.  状态转移方程
    
    ![ogyovzrz17-1690372796443.png][]
3.  初始化
    
    刚开始如果是买入状态`dp[0][0] = -prices[0]`
4.  填表
5.  返回值

AC代码：

class Solution 
    {
        
    public:
        int maxProfit(vector<int>& prices, int fee) 
        {
        
            int n = prices.size();
            vector<vector<int>> dp(n, vector<int>(2));
            dp[0][0] = -prices[0];
            for (int i = 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][0] + prices[i] - fee);
            }
            return max(dp[n - 1][0], dp[n - 1][1]);
        }
    };

### 7. 买卖股票的最佳时机 ||| ###

[题目链接][Link 7]

1.  状态表示
    
    `dp[i]`表示到i位置的最大利润，但是还分为几个状态
    
    `f[i][j]`表示到i是第j次买入的最大利润
    
    `g[i][j]`表示到i是第j次买入的最大利润
2.  状态转移方程
    
    ![zrwwmb104n-1690374918443.png][]
3.  初始化
    
    `f[0][0] = -prices[0], g[0][0] = 0`
4.  填表
    
    从上往下，每一行从左到右
5.  返回值
    
    卖出状态最后的几个中的最大值

AC代码：

class Solution 
    {
        
    public:
        const int N = 0x3f3f3f3f;
        int maxProfit(vector<int>& prices) 
        {
        
            int n = prices.size();
            vector<vector<int>> f(n, vector<int>(3, -N));
            auto g = f;
            f[0][0] = -prices[0], g[0][0] = 0;
            for (int i = 1; i < n; i++)
            {
        
                for (int j = 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]);
                }
            }
            int ret = 0;
            for (int i = 0; i < 3; i++)
            {
        
                ret = max(ret, g[n - 1][i]);
            }
            return ret;
        }
    };

### 8. 买卖股票的最佳时机 IV ###

[题目链接][Link 8]

1.  状态表示
    
    还是分为两个子状态
    
    `f[i][j]`表示到i位置买入状态第j次买股票的最大利润
    
    `g[i][j]`表示到i位置卖出状态第j次买股票的最大利润
2.  状态转移方程
    
    ![image-20230726205442099][]
3.  初始化
    
    `f[0][0] = -prices[0], g[0][0] = 0`
4.  填表
    
    从上到下，从左到右
5.  返回值
    
    返回所有行的最大值

AC代码：

class Solution {
        
    public:
        const int N = 0x3f3f3f3f;
        int maxProfit(int k, vector<int>& prices) {
        
            int n = prices.size();
            vector<vector<int>> f(n, vector<int>(k + 1, -N));
            auto g = f;
            f[0][0] = -prices[0], g[0][0] = 0;
            for (int i = 1; i < n; i++)
            {
        
                for (int j = 0; j <= k; 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]);
                }
            }
            int ret = 0;
            for (int i = 0; i <= k; i++)
            {
        
                ret = max(ret, g[n - 1][i]);
            }
            return ret;
        }
    };

[Link 1]: https://leetcode.cn/problems/the-masseuse-lcci/description/
[2vu4cjw7da-1690362953455.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/14/13bf785810b449b38b8802084e78f467.png
[Link 2]: https://leetcode.cn/problems/house-robber-ii/description/
[qx81yjpg3g-1690364303443.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/14/db49f35ed91441b0ad0b99d632d04ccc.png
[Link 3]: https://leetcode.cn/problems/delete-and-earn/
[Link 4]: https://leetcode.cn/problems/JEj789/
[wrmwgl7sbc-1690365960472.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/14/158e37bd4ac0422bbcf06856e814662a.png
[Link 5]: https://leetcode.cn/problems/best-time-to-buy-and-sell-stock-with-cooldown/
[bh40p1zbcb-1690367957450.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/14/911ea42aa7dd45d7bf54ae94b2931256.png
[Link 6]: https://leetcode.cn/problems/best-time-to-buy-and-sell-stock-with-transaction-fee/
[ogyovzrz17-1690372796443.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/14/9280e87dcea8401fa7a6587aa600955a.png
[Link 7]: https://leetcode.cn/problems/best-time-to-buy-and-sell-stock-iii/
[zrwwmb104n-1690374918443.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/14/2fbdaeea41a54f669d0d285f442756b0.png
[Link 8]: https://leetcode.cn/problems/best-time-to-buy-and-sell-stock-iv/
[image-20230726205442099]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/14/b5f677f55fe241f0a0a8053fde1b6115.png