专题二十_动态规划_简单多状态dp问题_买卖股票系列问题_算法专题详细总结

目录

动态规划

1. 按摩师（easy）

解析：

1.状态表达式：

2.状态转移方程

3.初始化

4.填表方向

5.返回值：

代码编写：

总结：

2. 打家劫舍II （medium）

解析：

代码编写：

总结：

3. 删除并获得点数（medium）

解析：

代码编写：

总结：

4. 粉刷房⼦（medium）

解析：

代码编写：

总结：

下面就是买卖股票类型，也是我当年的噩梦了：

5. 买卖股票的最佳时机含冷冻期（medium）

解析:

1.状态表达式：

2.状态转移方程：

3.初始化：

4.填表顺序：

5.返回值，只用返回最后一天的最大利润即可；

代码编写：

总结：

6. 买卖股票的最佳时期含⼿续费（medium）

解析：

编写代码：

总结：

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

解析：

代码编写：

总结：

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

 解析：

代码编写：

总结：

总结不易~本节对我的收获很大，希望对你也是~！！！

动态规划

在完成了前面动态规划相关内容的铺垫之后，我们已经对斐波那契模型以及路径问题有了清晰的认识。在此基础上，接下来我们将步入一个全新的章节 —— 简单多状态 dp 问题。

1. 按摩师（easy）

解析：

就是简单的dp问题，那我们来一步步分析清楚就能很快的解答：

1.状态表达式：

经验+题目意思

dp[i]表示：以i结尾的位置的最大服务时间

2.状态转移方程

3.初始化

初始f[i] 和 g[i] ，f[0] 就是初始化0位置要选的结果，即f[0]=nums[0]
g[0] 就是不选，不用进行初始化

4.填表方向

每次只有把i-1位置填了才能填当前位置，所填表方向从左往右填

5.返回值：

返回两种状态下的最大值即可

代码编写：

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

总结：

本题不是很难，主要就是要学会分析当前问题的情况，学会分类讨论，讨论出当前位置是选还是不选比较合适，从而分出两个函数来一个单独代表选的情况，一个单独代表不选

2. 打家劫舍II （medium）

解析：

1.状态表达式：

dp[i]表示：以i位置为结尾的最大利润

2.状态转移方程

仍然是设置f[i]表示当前位置选 跟 g[i]表示当前位置不选 两个表达式，这样就可以求出每一个位置选或者不选的不同的值，然后求出最后的最大值即可；

由于这一题是一个环形，所以就存在下面两种方案：

0位置选：0位置选了，1位置和n-1位置就不能被选了，那么这个数组的遍历范围就减小到[2,n-2]

0位置不选：那么1位置和n-1位置就有被选的资格，所以数组遍历范围就是[1,n-1];

那么为了多次创建数组，我们只需要封装一个函数rob1()每次传入数组的范围即可：

状态转移方程就是：

            f[i]=g[i-1]+nums[i];

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

3.初始化：

跟上一题一模一样的初始化，因为没有必要多开一个空间，又因为状态转移方程存在 n-1 所以每次只需要初始化传入的f[left]=nums[left] 然后从left+1开始遍历即可；

4.填表顺序：

依旧是从左往右填表

5.返回值

返回max(f[right],g[right]); 因为right位置是闭区间

代码编写：

class Solution {
public:
    int n;
    int rob(vector<int>& nums) {
        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)
    {
        if(left>right) return 0;
        vector<int> f(n);
        auto g=f;
        f[left]=nums[left];
        for(int i=left+1;i<=right;i++)
        {
            f[i]=g[i-1]+nums[i];
            g[i]=max(g[i-1],f[i-1]);
        }
        return max(f[right],g[right]);
    }
};

总结：

这一题值得好好反思总结跟上一题的区别，原理是一样的，但是细节问题很多好好对比一下还是收获满满的；

3. 删除并获得点数（medium）

题目意思很简单，就是每次选择一个数后比这个数大一和小的全部不能选，求出最大总和

解析：

我刚开始想构建一个完美的数组vector<pair<int,int>> hash；只存入nums里面的数字对应的总和，但是构建出来后，发现如果用上面的动态规划，那么就会跳过比如两个数字之间并不是相差1的大小，而是跳过了本来不应该跳过的数字，也就是说，就算那个数字不存在，也应该是0来表示

错误编写：

class Solution {
public:
    int deleteAndEarn(vector<int>& nums) {
        vector<pair<int,int>> hash;
        sort(nums.begin(),nums.end());
        int n=nums.size();
        for(int i=0;i<n;i++)
        {
            if(hash.size()==0)
            {
                hash.push_back({nums[i],nums[i]});
                continue;
            }
            if(nums[i]>hash.back().first) hash.push_back({nums[i],nums[i]});
            else hash.back().second+=nums[i];
        }

        for(auto e : hash) cout<<e.first<<" "<<e.second<<endl;

        n=hash.size();
        vector<int> f(n);
        auto g=f;
        f[0]=hash[0].second;
        for(int i=1;i<n;i++)
        {
            f[i]=g[i-1]+hash[i].second;
            g[i]=max(g[i-1],f[i-1]);
        }
        return max(f[n-1],g[n-1]);
    }
};

所以还是只能创建一个unordered_map<int,int> 来构建这个hash

1.状态表达式

通过上面的思路可以看出这一题就是前面的打家劫舍I问题，只需要把对应的数字求出对应的总和即可：

dp[i] 表示：以i位置为结尾的最大总和数

2.状态转移方程：

还是跟打家劫舍问题一样，设置两个数组，分别记录当前位置选还是不选的最终结果，然后分别取最大值

f[i]=g[i-1]+nums[i];

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

3.初始化：

任然是每次都要遍历i-1的位置，所以只需要初始化f[0]=hash[0],从1开始；

4.填表顺序：

从左往右

5.返回值

由于最后是[1,n]闭区间的位置，因为最后一个位置是hash里面最大值，所以开空间要开到ret的位置，也就是n+1个空间，最后返回max(f[n],g[n]);

代码编写：

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

总结：

这一题很细节，就是要学会问题的转换，能够把题目意思转换成我们所熟悉的打家劫舍问题，我记得我第一次做的时候就是暴力求解，删掉了当前位置的前一个值和后一个值，然后求最大值

4. 粉刷房⼦（medium）

解析：

1.状态表达式

dp问题就是为了表达所有的情况，求出最优解，所以设置一维dp只能表示每一行的最优解，而不能表示选取每一个格子后是否为最优解
设置二维:
dp[i][0]:表示在第i个房子下，用0号颜色情况下的所有粉刷最小费用
dp[i][1]:表示在第i个房子下，用1号颜色情况下的所有粉刷最小费用
dp[i][2]:表示在第i个房子下，用2号颜色情况下的所有粉刷最小费用

2.状态转移方程：

由于只有三个颜色，那么完全可以单独为每一个dp[i][0/1/2]单独求最小值：
即状态转移方程：是通过上一行能够挑出的两个颜色中选一个最小值在+当前房子需要的费用
            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];

3.初始化：

多加一行，初始化为0 即可，就是为了避免越界

4.填表顺序：

从上往下，从左往右填表

5.返回值：

返回最后一行的最小值即可

代码编写：

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

总结：

这一题需要考虑的很细致，了解到怎么样才能将每一个房子的每一个颜色都考虑进来，很值得反复思考，让我更加深刻的理解到，动态规划是一个能够得到所有情况的最优解的办法

下面就是买卖股票类型，也是我当年的噩梦了：

5. 买卖股票的最佳时机含冷冻期（medium）

解析:

这一题买卖股票一共分为3个阶段，“买入”，“可交易”（手上没有股票，也不处于冷冻期），“冷冻期”

那么我们要考虑每一个阶段的dp，就要单独把每一个阶段单独拿出来进行考虑，给每一个阶段进行编号：

“买入” --> 0

“可交易” --> 1

“冷冻期” --> 2

1.状态表达式：

dp[i][0]表示：第i天结束后，处于“买入”状态，此时的最大利润

dp[i][1]表示：第i天结束后，处于“可交易”状态，此时的最大利润

dp[i][2]表示：第i天结束后，处于“冷冻期”状态，此时的最大利润

2.状态转移方程：

由于状态太多了，必须要画图来理清楚，不能盲目写代码：

从上面的状态机可以看到，每种状态都表示当天的状态能否发生对应的变换；

对照状态机来书写状态转移方程：

            dp[i][0]=max(dp[i-1][0],dp[i-1][1]-p[i]);
            dp[i][1]=max(dp[i-1][1],dp[i-1][2]);
            dp[i][2]=dp[i-1][0]+p[i];

3.初始化：

我最开始式多开了一行，就是为了避免越界的问题：就让p[i-1]

dp[i][0]=max(dp[i-1][0],dp[i-1][1]-p[i-1]);

初始化多开的第一行为0，但是这里我没有考虑到第1行取最大值会取到0，本应该在dp[1][0] 的位置是应该只买入的时候，当前的状态应该是负值，但是变成了0，最后影响了结果

所以这题初始化很简单，不用多开，只需要考虑第一天的所有状态即可：

dp[0][0]表示第0天只买入，dp[0][0]=-p[0];

dp[0][1]表示第0天为可交易，dp[0][1]=0;

dp[0][2]表示第0天为冷冻期，就是当天买入，当天卖出，dp[0][0]=0；

所以只用初始化dp[0][0]=-p[0]即可；

4.填表顺序：

从左往右，从上往下，依次填3个状态的dp表

5.返回值，只用返回最后一天的最大利润即可；

代码编写：

class Solution {
public:
    int maxProfit(vector<int>& p) {
        int n=p.size();
        int ret=0;
        vector<vector<int>> dp(n+1,vector<int>(3));
        dp[0][0]=-p[0];
        for(int i=1;i<n;i++)
        {
            dp[i][0]=max(dp[i-1][0],dp[i-1][1]-p[i]);
            dp[i][1]=max(dp[i-1][1],dp[i-1][2]);
            dp[i][2]=dp[i-1][0]+p[i];
            if(i==n-1) ret=max(max(dp[i][0],dp[i][1]),dp[i][2]);
        }
        return ret;
    }
};

总结：

这一题的状态机就能很好的表达出上面是多状态dp问题，多状态dp，就是要逐个分析每个状态会发生的每一种情况，才能得到最优解

6. 买卖股票的最佳时期含⼿续费（medium）

解析：

有了上一题的经验，这一题就太好解决了

1.状态表达式：

这一题只有两个状态：

买入 -- > 0

可交易 --> 1

dp[i][0]表示：第i天时进行买入的最大利润

dp[i][1]表示：第i天时处于可交易状态的最大利润

2.状态转移方程：

根据上面的两个状态，来画出状态机，根据状态机来一步步秒杀状态转移方程

从买入到买入状态，就是当天什么也不干；从买入到卖出状态，就是卖掉手上的股票+p[i]，这里我们规定，到卖出一只股票算是一个完整的操作，我们就要在这个时候交手续费-fee

从卖出到卖出状态，就是当天什么也不干；从卖出到买入状态，就是当天在买入一只股票-p[i]

dp[i][0]=max(dp[i-1][0],dp[i-1][1]-p[i]);
dp[i][1]=max(dp[i-1][1],dp[i-1][0]+p[i]-fee);

3.初始化：

还是只用考虑dp[0][0]第0天的时候处于买入状态:dp[0][0]=-p[i];处于可交易状态时dp[0][1]=0;就是第0天不买也不卖

4.填表顺序：

从左往右，从上往下，依次填买入和可交易两个表

5.返回值：

返回最后一天的最大值

编写代码：

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

总结：

这类多状态dp问题只要画好状态机，就能迎刃而解，要耐心分析状态的每一种表示方式

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

解析：

1.状态表达式：

在分析dp状态的时候，考虑到每一个格子都有多种状态，当天可能会存在“买入” 和 “卖出”两种状态，在对每一种状态进行单独分析：

“买入” --> f[i][j]表示：第i天结束之后，完成了j次交易，此时处于“买入”状态下的，最大利润

“卖出” --> g[i][j]表示：第i天结束之后，完成了j次交易，此时处于“卖出”状态下的最大利润

这里就把每一种状态的每一天完成了几次交易分析的很透彻

2.状态转移方程：

首先就是画出状态机，然后再一步步分析每种状态的多种表示方式

这里初始化就一起顺带放在里面，为了避免初始化越界的问题把g[i][j]单独来出来考虑，当j-1>=0的时候再将g[i][j]进行比较取最大值

g[i][j] = g[i - 1][j];

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

4. 填表顺序：

从「上往下填」每⼀⾏，每⼀⾏「从左往右」，两个表「⼀起填」。

代码编写：

class Solution {
public:
    int maxProfit(vector<int>& p) {
        int n=p.size();
        vector<vector<int>> f(n,vector<int>(3,-0x3f3f3f));
        auto g=f;
        f[0][0]=-p[0],g[0][0]=0;
        int ret=0;
        for(int i=1;i<n;i++)
        {
            for(int j=0;j<=2;j++)
            {
                f[i][j]=max(f[i-1][j],g[i-1][j]-p[i]);
                g[i][j]=g[i-1][j];
                if(j-1>=0) g[i][j]=max(g[i][j],f[i-1][j-1]+p[i]);
                if(i==n-1) ret=max(g[i][j],ret);
            }
        }
        return ret;
    }
};

总结：

这题很难，很细，还需要自己下去多总结，多思考~

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

 解析：

1.状态表达式：

在分析dp状态的时候，考虑到每一个格子都有多种状态，当天可能会存在“买入” 和 “卖出”两种状态，在对每一种状态进行单独分析：

“买入” --> f[i][j]表示：第i天结束之后，完成了j次交易，此时处于“买入”状态下的，最大利润

“卖出” --> g[i][j]表示：第i天结束之后，完成了j次交易，此时处于“卖出”状态下的最大利润

这里就把每一种状态的每一天完成了几次交易分析的很透彻

2.状态转移方程：

首先就是画出状态机，然后再一步步分析每种状态的多种表示方式

这里初始化就一起顺带放在里面，为了避免初始化越界的问题把g[i][j]单独来出来考虑，当j-1>=0的时候再将g[i][j]进行比较取最大值

g[i][j] = g[i - 1][j];

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

4. 填表顺序：

从「上往下填」每⼀⾏，每⼀⾏「从左往右」，两个表「⼀起填」。

代码编写：

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

总结不易~本节对我的收获很大，希望对你也是~！！！