【动态规划】C++简单多状态dp问题（打家劫舍、粉刷房子、买卖股票的最佳时机...）

思路

• 题意分析

  1. 对于该题，我们首先知道按摩师在某个时间段可以选择服务或者不服务，即 两种状态 。
  2. 而每进行一次服务就需要休息一天，我们需要找到最优的服务策略：即预约时常最长。

所以我们创建两个dp数组，来进行状态转移方程的编写：

代码

class Solution {
public:int massage(vector<int>& nums) {int m = nums.size();// 边界条件if(m == 0) return 0;// dp[i]: 在i位置时的最长预约时间// f[i] 选择当前位置 g[i] 不选择当前位置(i位置)vector<int> f(m);auto g = f;// 初始化f[0] = nums[0]; // g[0] = 0; 默认为0for(int i = 1; i < m; ++i){f[i] = g[i-1] + nums[i];g[i] = max(f[i-1], g[i-1]);}return max(f[m-1], g[m-1]);}
};

思路

• 题意分析
  1. 对于该题，小偷对每一家可以选择偷或者不偷，即 两种状态 ；
     又相邻的房屋不能同时被闯入（数组首位也算相邻），找能偷窃的最大金额。
  2. 从上面的分析，可以看出来该题和按摩师一题很像，区别在于数组首尾位置不能同时选择。
  • 如何解决这一点？
    • 我们只需要分别算出来选择0位置和不选0位置的两种情况并求最大值即可。
    • 而其余部分和《按摩师》没有区别，下面简单写状态转移方程的分析：

代码

class Solution {
public:int rob(vector<int>& nums) {int n = nums.size();return max((nums[0] + _rob(nums, 2, n-2)), _rob(nums, 1, n-1));}// 打家劫舍I（按摩师） 的思路int _rob(vector<int>& nums, int left, int right){if(left > right) return 0; // 边界判断vector<int> f(nums.size());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(f[i-1], g[i-1]);}return max(f[right], g[right]);}
};

思路

• 题意分析
  1. 根据题意，我们可以知道，我们每次选择一个nums[i]删除并记录点数，后需要将相邻为1的数一并删除。
  2. 即不能同时统计相邻的位置的点数，很像按摩师（打家劫舍）的思路
• 我们可以对数组进行预处理：

如图所示，此时对arr进行之前的代码操作即可。

代码

class Solution {
public:int deleteAndEarn(vector<int>& nums) {const int N = 10001;// 预处理数组 - 下标i对应 i在nums中的的总和vector<int> arr(N);for(int num : nums) arr[num] += num;// 在arr数组上 进行打家劫舍的操作// 创建dp数组vector<int> f(N);auto g = f;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]);}
};

思路

• 题意分析
  1. 对于该题，我们知道相邻房子的颜色不能相同，而每间房子都可以涂三种颜色，即 三种状态 ，我们可以用一个二维数组dp[i][j]，其中j = 0, 1, 2分别代表三种颜色。

有了上面的思路，下面就可以进行解题了：

代码

class Solution {
public:int minCost(vector<vector<int>>& costs) {// dp[i][0] 在i层，刷红色漆时的最小花费// dp[i][1] 在i层，刷蓝色漆时的最小花费// dp[i][2] 在i层，刷绿色漆时的最小花费int m = costs.size(); // 只有三列 n = 3vector<vector<int>> dp(m+1, vector<int>(3));for(int i = 1; i <= m; ++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];}return min(min(dp[m][0], dp[m][1]), dp[m][2]);}
};

思路

• 题意分析
  1. 对于该题，每天的状态可能是：买入、卖出、冷冻期；相当于共有 三种状态 ，我们按照《粉刷房子》的思路创建二维dp数组。
  2. 当一天处于卖出状态时，实际上就是可交易，对于《粉刷房子》的要求是不能有连续相同的颜色，对于本题的要求自然不能有连续相同的状态，其他的通过下图得出：

下面画图找状态表示，以及通过三种状态的关系写状态转移方程：

• 关于初始化：
  1. dp[0][0] = -p[0] 第一天为“买入”，买入后此时钱包是负的
  2. dp[0][1] = dp[0][0] = 0
• 关于返回值
  • max(dp[m - 1][1], dp[m - 1][2])：最后一天可以是卖出状态，可以是冷冻期、不可以是买入状态，两状态取最大值。

代码

class Solution {
public:int maxProfit(vector<int>& prices) {// dp[i][0]: 第i天时，为“买入状态“的最大利润// dp[i][1]: 第i天时，为“可交易状态”的最大利润// dp[i][2]: 第i天时，为“冷冻期”的最大利润int m = prices.size();vector<vector<int>> dp(m, vector<int>(3));dp[0][0] = -prices[0]; // 初始化for(int i = 1; i < m; ++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(dp[m - 1][1], dp[m - 1][2]); // dp[m-1][0]；最后不能是买入状态}
};

思路

• 题意分析

  1. 根据题目，我们知道每一天有“买入”和“卖出”，即 两种状态 ，可以创建两个dp数组。
  2. 本题与前面《冷冻期》的差别在于，该题在卖出后，不存在冷冻期，第二天可以继续交易，但是需要考虑手续费，下面根据图得出关系：

• 下面通过分析两种状态的关系，写出状态转移方程：
  

• 关于初始化：

  • 根据买入状态与卖出状态，f[0] = -price[0], g[0] = 0;

• 填表顺序：

  • 两个表均从左向右

• 返回值

  • max(f[n-1], g[n-1])

代码

class Solution {
public:int maxProfit(vector<int>& prices, int fee) {int m = prices.size();// 预处理dp数组vector<int> f(m);auto g = f;// 初始化f[0] = -prices[0];for(int i = 1; i < m; ++i){f[i] = max(g[i-1] - prices[i], f[i-1]);g[i] = max(f[i-1] + prices[i] - fee, g[i-1]);}return g[m-1]; // 利润最大，自然最后一天不能选择买入，即不能是f[m-1]}
};

思路

• 题意分析

  1. 本题不需要考虑冷冻期、手续费，但加上了一个限制条件，即最多只能完成两笔交易，求最大利润（进行0次交易也是可以的，只要利润最大）
  2. 此时我们不但需要考虑某一天的状态，也需要考虑当前完成了几笔交易

• 首先找状态表示与状态转移方程：
  

• 随后内容初始化以及其余细节问题：

代码

class Solution {
public:const int INF = 0x3f3f3f3f; // INT_MAX的1/2int maxProfit(vector<int>& prices) {int n = prices.size();// 创建dp数组vector<vector<int>> f(n, vector<int>(3, -INF));auto g = f; // i位置时，进行了j笔交易，最后状态为卖出的最大利润// 初始化元素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] = max(g[i-1][j], f[i-1][j-1] + prices[i])：需要初始化g[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 k = 0; k < 3; ++k)ret = max(ret, g[n - 1][k]);return ret;}
};

思路

• 题意分析 相比于前一题，该题的改动就是将买卖次数定为k次，其余条件不变，求最大利润。
• 故只需更改之前代码中的条件即可，将次数设为k次。
• 不再画图，思路同前。

代码

class Solution {
public:const int INF = 0x3f3f3f3f;int maxProfit(int k, vector<int>& prices) {int n = prices.size();k = min(k, n/2); // 最多交易n/2次vector<vector<int>> f(n, vector<int>(k+1, -INF)); // 第i天交易了j次、且为买入状态的最大利润auto g = f; // 第i天交易了j次、且为“卖出”状态的最大利润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]); // f[i-1][j-1] j-1: 记录一次交易次数}int ret = 0;for(int j = 0; j <= k; ++j)ret = max(ret, g[n-1][j]);return ret;}
};