闲话少叙，直接开始我们的第十三天语法学习
目录
第一题
题目链接
题目解析
代码原理
代码编写
class Solution {
public:
int minCost(vector<vector<int>>& costs) {
int n = costs.size();
//建表
vector<vector<int>> dp(n + 1,vector<int>(3));
//填表
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];
}
return min(min(dp[n][0],dp[n][1]),dp[n][2]);
}
};
注意：这里的初始化部分，我已经将其省略，因为vector初始化会自动初始化为0，因此可以省略，而不是不需要初始化
第二题
题目链接
309. 买卖股票的最佳时机含冷冻期 - 力扣（LeetCode）
题目解析
代码原理
代码编写
class Solution {
public:
int maxProfit(vector<int>& prices) {
int n = prices.size();
//建表
vector<vector<int>> dp(n, vector<int>(3));
//初始化
dp[0][0] = -prices[0];
//填表
for(int i = 1; i < n; 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[n - 1][1], dp[n - 1][2]);
}
};
第三题
题目链接
714. 买卖股票的最佳时机含手续费 - 力扣（LeetCode）
题目解析
代码原理
代码编写
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 g[n - 1];
}
};
今日总结：
1. 三道题对于初学者而言都是相对比较绕的
2.第二题和第三题涉及到多个状态的，我们在状态表示部分一定要标清楚dp[i]有几种状态，在写状态转移方程时也需要通过画图（也就是状态积）进行分析
3.如何看懂状态积的小技巧：箭头位置表示第i天，它的起始位置表示第i - 1天
那么本篇文章算法的学习就先到这里，我们下期文章再见！！！
记得一键三联哦！！！
