动态规划——多状态动态规划问题

目录

一、打家劫舍 

二、打家劫舍 II 

三、删除并获得点数

四、粉刷房子 

五、买卖股票的最佳时机含冷冻期

六、买卖股票的最佳时机含手续费

七、买卖股票的最佳时机III

八、买卖股票的最佳时机IV


一、打家劫舍 

打家劫舍

第一步:确定状态表示

当我们每次偷到第i间房子时,我们存在两种状态,即可以选择偷或者不偷该房子的金额。所以我们需要有两张dp表。

f[ i ] 表示偷到第 i 间房子时,小偷选择偷第  i 间房子的金额时,偷窃到的总金额最大。g[ i ]表示偷到第 i 间房子时,小偷选择不偷第  i 间房子的金额时,偷窃到的总金额最大。

第二步:推出状态转移方程

第三步:初始化dp表

我们在使用状态转移方程时,会用到 i-1位置的值,那么如果 i 为0的话,就会有越界访问的问题,所以我们需要初始化,f[0] = nums[0],g[i] = 0。

填表顺序:因为在填写 i 位置的值时,我们要用到 i-1位置的值,所以需要从左往右依次填写。

最后的返回值:我们要返回光顾完所有房子后,所能偷到的最大金额,所以需要返回f[n-1] 和 g[i-1]两者的最大值。

解题代码:

class Solution 
{
public:
    int rob(vector<int>& nums) 
    {
        int n = nums.size();
        vector<int> f(n);
        vector<int> g(n);
        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]);
    }
};

 


二、打家劫舍 II 

打家劫舍II

打家劫舍II和打家劫舍问题唯一不同的是,这道题的房子是围成一个圈的。我们可以将它转换成打家劫舍问题去处理。

其他方法就和打家劫舍问题一样了。 

返回值就是上面两种情况的最大值。

解题代码:

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

    int rob1(vector<int>& nums, int left, int right)
    {
        int n = nums.size();
        if(left > right)
            return 0;

        vector<int> f(n);
        vector<int> g(n);
        f[left] = nums[left]; // 区间的起始位置是left
        for(int i = left; i <= right; i++)
        {
            f[i] = g[i-1] + nums[i];
            g[i] = max(g[i-1], f[i-1]);
        }
        return max(g[right], f[right]); // 区间的最右是right
    }
};


三、删除并获得点数

删除并获得点数

预处理:我们需要注意题目说明中的这一句:选择任意一个 nums[i] ,删除它并获得 nums[i] 的点数。之后,你必须删除所有等于 nums[i] - 1 和 nums[i] + 1 的元素。 

也就是说,你在拿到nums[i]的点数后,就不能选择它前一个和后一个元素了。比如,nums[i]为5,拿到5这个点数后,你就不能再拿3和4了。这个要求是不是又和打家劫舍很像了。所以我们最终还是将这个问题转换成了打家劫舍问题。

比如对于示例2:

解题代码:

class Solution 
{
public:
    int deleteAndEarn(vector<int>& nums) 
    {
        int arr[10001] = {0};
        for(auto x : nums)
            arr[x] += x;

        vector<int> f(10001);
        vector<int> g(10001);
        f[0] = arr[0];
        for(int i = 1; i < 10001; i++)
        {
            f[i] = g[i-1] + arr[i];
            g[i] = max(g[i-1], f[i-1]);
        }
        return max(g[10000], f[10000]);
    }
};


四、粉刷房子 

粉刷房子

第一步:确定状态表示

红:0,蓝:1,绿:2。

dp[i][j]:表示刷到第i个房子时,将其涂成第j种颜色时的最小花费。

第二步:推出状态转移方程

第三步:初始化dp表

在使用dp表时,要使用i-1,所以 i == 0时,就会发生越界访问的问题。所以初始化,

dp[0][0] =  costs[0][0],dp[0][1] = costs[0][1],dp[0][2] = costs[0][2]。

填表顺序:从上向下,从左到右

最后的返回值是最后一行的最大值。

解题代码:

class Solution 
{
public:
    int minCost(vector<vector<int>>& costs) 
    {
        int m = costs.size(), n = costs[0].size();
        // 红:0,蓝:1,绿:2
        // dp[i][j]:表示刷到第i个房子时,将其涂成第j种颜色时的最小花费
        vector<vector<int>> dp(m, vector<int>(3));
        dp[0][0] = costs[0][0], dp[0][1] = costs[0][1], dp[0][2] = costs[0][2];
        for(int i = 1; i < m; i++)
        {
            dp[i][0] = min(dp[i-1][1], dp[i-1][2]) + costs[i][0];
            dp[i][1] = min(dp[i-1][0], dp[i-1][2]) + costs[i][1];
            dp[i][2] = min(dp[i-1][0], dp[i-1][1]) + costs[i][2];
        }
        return min(dp[m-1][0], min(dp[m-1][1], dp[m-1][2]));
    }
};


五、买卖股票的最佳时机含冷冻期

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

第一步:确定状态表示

根据题意和示例,大的状态表示就是在第i天结束后,所获得的最大利润,而对于第i天来说,我们又有三种可能的状态:卖出,买入,冷冻期。

卖出状态:0,买入状态:1,冷冻期:2

所以说,dp[i][j]:表示第 i 天结束后,处于第 j 种状态时,所获的最大利润。

dp[i][0] 表示: 第 i 天结束之后,处于卖出状态,此时的最大利润。

dp[i][1] 表示: 第 i 天结束之后,处于买入状态,此时的最大利润。

dp[i][2] 表示: 第 i 天结束之后,处于冷冻期状态,此时的最大利润。

第二步:推出状态转移方程

对于上面的核心图,我们对卖出状态进行举例解释一下:

如果在第 i 天结束后处于卖出状态,需要看 i - 1 天是什么状态然后怎么做能够满足第 i 天结束处于卖出状态。

如果第 i - 1 天结束处于卖出状态,那第 i 天什么也不干,依旧处于卖出状态。

如果第 i - 1 天结束处于冷冻期,也就是说第 i 天不能进行任何操作,无法购买股票,当第 i 天结束后,就会结束冷冻期,进入卖出状态。

第三步:初始化dp表,dp[0][1] = -prices[0]。

从左往右,从上向下依次填表,最后返回最后一天的三种状态中的最大值。

解题代码:

class Solution 
{
public:
    int maxProfit(vector<int>& prices) 
    {
        int m = prices.size();
        vector<vector<int>> dp(m, vector<int>(3));
        dp[0][1] = -prices[0];
        // 卖:0,买:1,冷冻:2
        for(int i = 1; i < m; i++)
        {
            dp[i][0] = max(dp[i-1][0], dp[i-1][2]);
            dp[i][1] = max(dp[i-1][1], dp[i-1][0]-prices[i]);
            dp[i][2] = dp[i-1][1]+prices[i];
        }
        return max(max(dp[m-1][0], dp[m-1][1]), dp[m-1][2]);
    }
};

 


六、买卖股票的最佳时机含手续费

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

第一步:确定状态表示

根据题意,每一天都可能存在两种状态,买入状态和卖出状态。

所以,f[i]:表示第 i 天结束后,处于买入状态时,所获的最大利润。g[i]:表示第 i 天结束后,处于卖出状态时,所获的最大利润。

需要注意的是,每次卖出股票,需要支付手续费。

第二步:推出状态转移方程

第三步:初始化dp表,f[0] = -prices[0]。

填表顺序为从左往右依次填写,g[i]和f[i]一起填写。最后的返回值是f[m-1]和f[m-1]中的最大值。

解题代码:

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

 


七、买卖股票的最佳时机III

买卖股票的最佳时机III

第一步:确定状态表示

首先,仍然是 dp[i] 表示第 i 天结束后所获得的最大利润。每一天有两种状态,卖出和买入状态。

而这道题和之前的题目不同的就是,它有交易次数的限制,只能够完成两笔交易。所以对于每一天来说,在卖出和买入状态之下,还有一种状态,那就是一直到第 i 天的交易次数。

所以,dp[i][j] :表示第 i 天结束后,完成了 j 次交易后,所获得的最大利润。0表示完成了0次交易,1表示完成了1次交易,2表示完成了2次交易。

f[i][j] :表示第 i 天结束后,处于买入状态时,完成了 j 次交易后,所获得的最大利润。

g[i][j] :表示第 i 天结束后,处于卖出状态时,完成了 j 次交易后,所获得的最大利润。

第二步:推出状态转移方程

第三步:初始化dp表

填表顺序为从左往右,从上往下依次填写,g[i]和f[i]一起填写。 

解题代码:

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

        int ret = 0;
        for(int i = 0; i < 3; i++)
        {
            if(g[m-1][i] > ret)
                ret = g[m-1][i];
        }
        return ret;
    }
};

 


八、买卖股票的最佳时机IV

买卖股票的最佳时机IV

这一道题的思路,和买卖股票的最佳时机III一模一样,只是把最多交易次数限定成了一个未知数。我们所有的解题方法都与他相同。

解题代码:

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

 

上一篇:场内期权交易规则及方式详解


下一篇:ansible自动化运维,一些基础命令、更方便掌握ansible。