文章目录
前言
1. 前言 - 理解动态规划算法
关于 动态规划的理解 与例题，点击👇
有了上面的经验，我们来解下面 简单多状态的dp问题 ：
2. 关于 简单多状态的dp问题
对于该类问题，对于某一时刻、位置一般有 多种状态 （>=2），所以我们一般会采用一些方法：
- 创建多个dp数组表示每种状态
- 创建多维数组表示时刻的不同状态
2.5 例题
下面的算法题为一道例题，通过该题我们看对该类题的解法进行熟悉。
按摩师/打家劫舍
思路
题意分析
- 对于该题，我们首先知道按摩师在某个时间段可以选择服务或者不服务，即 两种状态 。
- 而每进行一次服务就需要休息一天，我们需要找到最优的服务策略：即预约时常最长。
所以我们创建两个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; 默认为0
for(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]);
}
};
3. 算法题
3.1_打家劫舍II
思路
- 题意分析
- 对于该题，小偷对每一家可以选择偷或者不偷，即 两种状态 ；
又相邻的房屋不能同时被闯入（数组首位也算相邻），找能偷窃的最大金额。 - 从上面的分析，可以看出来该题和按摩师一题很像，区别在于数组首尾位置不能同时选择。
- 如何解决这一点？
- 我们只需要分别算出来选择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]);
}
};
3.2_删除并获得点数
思路
- 题意分析
- 根据题意，我们可以知道，我们每次选择一个nums[i]删除并记录点数，后需要将相邻为1的数一并删除。
- 即不能同时统计相邻的位置的点数，很像按摩师（打家劫舍）的思路
- 我们可以对数组进行预处理：
如图所示，此时对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]);
}
};
3.3_粉刷房子
思路
- 题意分析
- 对于该题，我们知道相邻房子的颜色不能相同，而每间房子都可以涂三种颜色，即 三种状态 ，我们可以用一个二维数组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 = 3
vector<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]);
}
};
3.4_买卖股票的最佳时机含冷冻期
思路
- 题意分析
- 对于该题，每天的状态可能是：买入、卖出、冷冻期；相当于共有 三种状态 ，我们按照《粉刷房子》的思路创建二维dp数组。
- 当一天处于卖出状态时，实际上就是可交易，对于《粉刷房子》的要求是不能有连续相同的颜色，对于本题的要求自然不能有连续相同的状态，其他的通过下图得出：
下面画图找状态表示，以及通过三种状态的关系写状态转移方程：
- 关于初始化：
- dp[0][0] = -p[0] 第一天为“买入”，买入后此时钱包是负的
- 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]；最后不能是买入状态
}
};
3.5_买卖股票的最佳时机含手续费
思路
题意分析
- 根据题目，我们知道每一天有“买入”和“卖出”，即 两种状态 ，可以创建两个dp数组。
- 本题与前面《冷冻期》的差别在于，该题在卖出后，不存在冷冻期，第二天可以继续交易，但是需要考虑手续费，下面根据图得出关系：
下面通过分析两种状态的关系，写出状态转移方程：
关于初始化：
- 根据买入状态与卖出状态，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]
}
};
3.6_买卖股票的最佳时机III
思路
题意分析
- 本题不需要考虑冷冻期、手续费，但加上了一个限制条件，即最多只能完成两笔交易，求最大利润（进行0次交易也是可以的，只要利润最大）
- 此时我们不但需要考虑某一天的状态，也需要考虑当前完成了几笔交易
首先找状态表示与状态转移方程：
随后内容初始化以及其余细节问题：
代码
class Solution {
public:
const int INF = 0x3f3f3f3f; // INT_MAX的1/2
int 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;
}
};
3.7_买卖股票的最佳时机IV
思路
- 题意分析 相比于前一题，该题的改动就是将买卖次数定为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;
}
};