动态规划专训3——简单多状态

动态规划中，许多时候一个状态并不能表示出所有情况，往往这个时候需要用多状态来表示，以解决问题

1.按摩师

面试题 17.16. 按摩师

一个有名的按摩师会收到源源不断的预约请求，每个预约都可以选择接或不接。在每次预约服务之间要有休息时间，因此她不能接受相邻的预约。给定一个预约请求序列，替按摩师找到最优的预约集合（总预约时间最长），返回总的分钟数

1.状态表示：用 f [ i ]表示以 i 位置结尾，且 i 必选的最大利润

用 g [ i ]表示以 i 位置结尾，且 i 不选的最大利润

2.状态转移方程：f [ i ] = g [ i - 1 ] + nums[ i ]

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

3.初始化：f [ 0 ] = num[ 0 ]

4.填表顺序：从左往右，两个表一起填

5.返回值：max( f [ n - 1 ] , g [ n - 1 ] )

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];
        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]);
    }
};

这是ac代码

2.打家劫舍II

213. 打家劫舍 II

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

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

这道题是上面题目的加强版，我们不妨使用上面已有的基础上做这道题，分0位置选与不选，将环形问题转换为非环形问题，用上面题目的思路解决问题

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

        return max(f[right], g[right]);
    }

    int rob(vector<int>& nums) 
    {
        int n = nums.size();
        return max(_rob(nums, 1, n - 1), _rob(nums, 2, n - 2) + nums[0]);
    }
};

这是ac代码

3.删除并获得点数

740. 删除并获得点数

给你一个整数数组 nums ，你可以对它进行一些操作。

每次操作中，选择任意一个 nums[i] ，删除它并获得 nums[i] 的点数。之后，你必须删除所有等于 nums[i] - 1 和 nums[i] + 1 的元素。

开始你拥有 0 个点数。返回你能通过这些操作获得的最大点数

思路与打家劫舍思想一样，我们只需将原数组处理得到一个新数组，这个新数组内存的值是对应下标之和，再做一次打家劫舍即可

class Solution {
public:
    int deleteAndEarn(vector<int>& nums) 
    {
        int n = 10001;
        vector<int> arr(n);
        for(int e : nums)
            arr[e] += e;

        vector<int> f(n), g(n);
        f[0] = arr[0];
        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(f[n - 1], g[n - 1]);
    }
};

这是ac代码

4.粉刷房子

LCR 091. 粉刷房子

假如有一排房子，共 n 个，每个房子可以被粉刷成红色、蓝色或者绿色这三种颜色中的一种，你需要粉刷所有的房子并且使其相邻的两个房子颜色不能相同。

当然，因为市场上不同颜色油漆的价格不同，所以房子粉刷成不同颜色的花费成本也是不同的。每个房子粉刷成不同颜色的花费是以一个 n x 3 的正整数矩阵 costs 来表示的。

例如，costs[0][0] 表示第 0 号房子粉刷成红色的成本花费；costs[1][2] 表示第 1 号房子粉刷成绿色的花费，以此类推。

请计算出粉刷完所有房子最少的花费成本

1.状态表示：用 f [ i ]表示以 i 位置结尾，且 i 位置红色的最小花费

用 g [ i ]表示以 i 位置结尾，且 i 位置蓝色的最小花费

用 h [ i ]表示以 i 位置结尾，且 i 位置绿色的最小花费

2.状态转移方程：

f [ i ] = min( g[ i - 1 ], h[ i - 1 ] ) + costs[ i ][ 0 ];

g [ i ] = min(f [ i - 1 ] , h[ i - 1] ) + costs[ i ][ 1 ];

h [ i ] = min( f [ i - 1 ], g[ i - 1] ) + costs[ i ][ 2 ];

3.初始化：

f[0] = costs[0][0];

g[0] = costs[0][1];

h[0] = costs[0][2];

4.填表顺序：从左往右，三个表一起填

5.返回值：min( f [ n - 1 ] , min( g[ n - 1 ], h [ n - 1 ] ) )

class Solution {
public:
    int minCost(vector<vector<int>>& costs) 
    {
        int n = costs.size();
        vector<int> f(n), g(n), h(n);
        f[0] = costs[0][0];
        g[0] = costs[0][1];
        h[0] = costs[0][2];

        for(int i = 1; i < n; ++i)
        {
            f[i] = min(g[i - 1], h[i - 1]) + costs[i][0];
            g[i] = min(f[i - 1], h[i - 1]) + costs[i][1];
            h[i] = min(f[i - 1], g[i - 1]) + costs[i][2];
        }

        return min(f[n - 1], min(g[n - 1], h[n - 1]));
    }
};

这是ac代码

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

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

给定一个整数数组prices，其中第 prices[i] 表示第 i 天的股票价格。

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

卖出股票后，你无法在第二天买入股票 (即冷冻期为 1 天)。

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

1.状态表示：用 f [ i ]表示以 i 天结尾，且处于买入期的最大利润（持有）

用 g [ i ]表示以 i 天结尾，且处于冷冻期的最大利润

用 h [ i ]表示以 i 天结尾，且处于卖出期的最大利润（可交易）

2.状态转移方程：

f [ i ] = max( f [ i - 1 ] , h[ i - 1 ] - prices[ i ] )

g [ i ] = f [ i - 1 ] + prices[ i ]

h[ i ] = max( h[ i - 1 ], g[ i - 1] )

3.初始化：

f[ 0 ] = - prices[ 0 ]

4.填表顺序：从左往右，三个表一起填

5.返回值：max(f [ n - 1 ], max( g[ n - 1 ], h [ n - 1 ] ) )

class Solution {
public:
    int maxProfit(vector<int>& prices) 
    {
        int n = prices.size();
        vector<int> f(n);   //买入期（持有）
        vector<int> g(n);   //冷冻期
        vector<int> h(n);   //卖出期（可交易）

        f[0] = - prices[0];
        for(int i = 1; i < n; ++i)
        {
            f[i] = max(f[i - 1], h[i - 1] - prices[i]);
            g[i] = f[i - 1] + prices[i];
            h[i] = max(h[i - 1], g[i - 1]);
        }

        return max(f[n - 1], max(g[n - 1], h[n - 1]));
    }
};

这是ac代码

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

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

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

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

返回获得利润的最大值。

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

1.状态表示：用 f [ i ]表示以 i 天结尾，且处于买入期的最大利润（持有）

用 g [ i ]表示以 i 天结尾，且处于卖出期的最大利润（可交易）

2.状态转移方程：

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

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

3.初始化：

f [ 0 ] = - prices[ 0 ]

4.填表顺序：从左往右，两个表一起填

5.返回值：max( f[ n - 1 ], g [ n - 1 ] )

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

        return max(f[n - 1], g[n - 1]);
    }
};

这是ac代码

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

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

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

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

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

1.状态表示：用 f [ i ][ j ]表示以 i 天结尾，交易次数为 j ，且处于买入期的最大利润（持有）

用 g [ i ][ j ]表示以 i 天结尾，交易次数为 j ，且处于卖出期的最大利润（可交易）

2.状态转移方程：

f [ i ][ j ] = max( f [ i - 1 ][ j ], g[ i - 1 ][ j ] - prices[ i ] )

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

3.初始化：

f[0][0] = - prices[0]

g[0][0] = 0

4.填表顺序：从左往右，从上往下两个表一起填

5.返回值：g表中最后一列的最大值（小于0则返回0）

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

        int ret = 0;
        for(int j = 0; j < 3; ++j)
            ret = max(ret, g[n - 1][j]);
        return ret;
    }
};

这是ac代码

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

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

给你一个整数数组 prices 和一个整数 k ，其中 prices[i] 是某支给定的股票在第 i 天的价格。

设计一个算法来计算你所能获取的最大利润。你最多可以完成 k 笔交易。也就是说，你最多可以买 k 次，卖 k 次。

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

1.状态表示：用 f [ i ][ j ]表示以 i 天结尾，交易次数为 j ，且处于买入期的最大利润（持有）

用 g [ i ][ j ]表示以 i 天结尾，交易次数为 j ，且处于卖出期的最大利润（可交易）

2.状态转移方程：

f [ i ][ j ] = max( f [ i - 1 ][ j ], g[ i - 1 ][ j ] - prices[ i ] )

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

3.初始化：

f[0][0] = - prices[0]

g[0][0] = 0

4.填表顺序：从左往右，从上往下两个表一起填

5.返回值：g表中最后一列的最大值（小于0则返回0）

思路与上面题目一样，重点是细节处理

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

        int ret = 0;
        for(int j = 0; j <= k; ++j)
            ret = max(ret, g[n - 1][j]);
        return ret;
    }
};

这是ac代码