一个有名的按摩师会收到源源不断的预约请求，每个预约都可以选择接或不接。在每次预约服务之间要有休息时间，因此她不能接受相邻的预约。给定一个预约请求序列，替按摩师找到最优的预约集合（总预约时间最长），返回总的分钟数。
注意：本题相对原题稍作改动
示例 1：
输入： [1,2,3,1]
输出： 4
解释： 选择 1 号预约和 3 号预约，总时长 = 1 + 3 = 4。示例 2：
输入： [2,7,9,3,1]
输出： 12
解释： 选择 1 号预约、 3 号预约和 5 号预约，总时长 = 2 + 9 + 1 = 12。示例 3：
输入： [2,1,4,5,3,1,1,3]
输出： 12
解释： 选择 1 号预约、 3 号预约、 5 号预约和 8 号预约，总时长 = 2 + 4 + 3 + 3 = 12。解题思路
接下来我们接触的这种类型的题目会和以前稍微不同，因为这种类型的动态规划，涉及到多种状态的问题，比如这道题就会出现两种状态！但是我们在分析的时候，还是用我们那五部曲来解决它！
状态表示和状态转移方程推导如下图：
由上图可知，我们的状态转移方程和以前不同，现在是有两条，如下：
select[i] = uncheck[i - 1] + nums[i]; // 选i的情况
uncheck[i] = max(select[i - 1], uncheck[i - 1]); // 不选i的情况 接下来就是初始化问题，如下图所示：
并且这道题并不需要我们去添加虚拟位置，因为我们初始了下标为 0 的位置，所以开始遍历的位置是从下标为 1 的元素开始的，而状态转移方程中只涉及到对 i-1 处的状态，所以不需要添加虚拟位置，也不会越界！
还需要注意的是，我们图中画的虽然是用一个数组来表示两种状态，但是在实现的时候，其实是可以用两个数组，一个表示 select 状态的数组，一个表示 uncheck 状态的数组来进行编程，所以最后的返回值就是在这两个数组中的最后一个元素中选出最大的！（也就是我们一直都考虑了选和不选的情况！）
填表顺序就是从左往右填写！
class Solution {
public:
int massage(vector<int>& nums) {
int n = nums.size();
if(n == 0) // 处理特殊条件
return 0;
// 创建对应的dp表，不需要添加虚拟位置
vector<int> select(n, 0);
vector<int> uncheck(n, 0);
// 初始化，uncheck不需要，因为上面创建的时候已经初始化为0了
select[0] = nums[0];
// 从左往右填表，从下标为1处开始
for(int i = 1; i < n; ++i)
{
select[i] = uncheck[i-1] + nums[i]; // i处必选的情况
uncheck[i] = max(select[i-1], uncheck[i-1]); // i处不选的情况
}
// 返回的是两个dp表最后一个元素的最大值！
return max(select[n-1], uncheck[n-1]);
}
};2、打家劫舍Ⅰ（medium）
你是一个专业的小偷，计划偷窃沿街的房屋。每间房内都藏有一定的现金，影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。
给定一个代表每个房屋存放金额的非负整数数组，计算你 不触动警报装置的情况下 ，一夜之内能够偷窃到的最高金额。
示例 1：
输入：[1,2,3,1]
输出：4
解释：偷窃 1 号房屋 (金额 = 1) ，然后偷窃 3 号房屋 (金额 = 3)。
偷窃到的最高金额 = 1 + 3 = 4 。示例 2：
输入：[2,7,9,3,1]
输出：12
解释：偷窃 1 号房屋 (金额 = 2), 偷窃 3 号房屋 (金额 = 9)，接着偷窃 5 号房屋 (金额 = 1)。
偷窃到的最高金额 = 2 + 9 + 1 = 12 。提示：
1 <= nums.length <= 1000 <= nums[i] <= 400
解题思路
这道题的大体思路和上面的按摩师题目是类似的，分为两种状态去解析，如下图所示：
还有剩下的初始化问题、填表顺序和返回值问题，都用图片形式展现：
class Solution {
public:
int rob(vector<int>& nums) {
// 创建dp表
int n = nums.size();
vector<int> steal(n, 0);
vector<int> nosteal(n, 0);
// 初始化
steal[0] = nums[0];
// 填表
for(int i = 1; i < n; ++i)
{
steal[i] = nosteal[i - 1] + nums[i];
nosteal[i] = max(steal[i - 1], nosteal[i - 1]);
}
// 返回两种可能状态的最大值
return max(steal[n-1], nosteal[n-1]);
}
};3、打家劫舍Ⅱ（medium）
你是一个专业的小偷，计划偷窃沿街的房屋，每间房内都藏有一定的现金。这个地方所有的房屋都 围成一圈 ，这意味着第一个房屋和最后一个房屋是紧挨着的。同时，相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警 。
给定一个代表每个房屋存放金额的非负整数数组，计算你 在不触动警报装置的情况下 ，今晚能够偷窃到的最高金额。
示例 1：
输入：nums = [2,3,2]
输出：3
解释：你不能先偷窃 1 号房屋（金额 = 2），然后偷窃 3 号房屋（金额 = 2）, 因为他们是相邻的。示例 2：
输入：nums = [1,2,3,1]
输出：4
解释：你可以先偷窃 1 号房屋（金额 = 1），然后偷窃 3 号房屋（金额 = 3）。
偷窃到的最高金额 = 1 + 3 = 4 。示例 3：
输入：nums = [1,2,3]
输出：3提示：
1 <= nums.length <= 1000 <= nums[i] <= 1000
解题思路
这道题和上面的 打家劫舍Ⅰ 的唯一区别，就是它的首尾是相连的，相当于一个环形队列！也就是说，如果我们在第一个位置选择偷，那么最后一个位置是不能偷的；如果第一个位置不偷的话，那么最后一个位置是可偷可不偷的！
仅仅是这个区别而已，所以我们只需要分析一下这种情况，然后复用我们上面写的 打家劫舍Ⅰ 的代码稍微修改一下就行了！
下面我们来分析一下首尾的情况：
- 首先我们要明白，我们不需要都得首尾进行判断，只需要对首部进行情况分析即可，因为我们最后要到达的是尾部位置，而此时首部是已经走过的了，所以其实影响尾部的就是首部，所以我们分析首部的时候，已经就相当于分析了尾部的情况，这点要清楚！
- 如果首部选择偷：
- 此时尾部就不能偷了，也就是说，我们能偷的 下标范围 就局限于 [2, n-2] 了。
- 为什么是从 2 开始呢，因为首部偷了，那么不仅尾部不能偷，首部的下一个元素也就是下标为 1 的元素也不能偷了，所以从 2 开始！
- 为什么是到 n-2 结束呢，因为要注意这是下标范围，最后一个元素是 n-1，因为它不能偷，所以能偷的范围就是到它的前一个下标 n-2 的元素！
- 如果选择选择不偷：
- 此时尾部是可以偷或者不偷的，而且首部的下一个下标 1 处的元素也是可以偷或者不偷的，所以能偷的 下标范围 就局限于 [1, n-1] 了！
- 此时尾部是可以偷或者不偷的，而且首部的下一个下标 1 处的元素也是可以偷或者不偷的，所以能偷的 下标范围 就局限于 [1, n-1] 了！
- 如果首部选择偷：
考虑完这两种情况，我们就可以开始写代码了，因为在能偷的下标范围内，其实代码实现就和 打家劫舍Ⅰ 是一样的，所以这里就不再详细讲解，具体的可以参考上面的笔记！
只不过我们需要将 打家劫舍Ⅰ 的代码稍微修改一下，具体的参考代码：
class Solution {
public:
// 主函数
int rob(vector<int>& nums) {
int n = nums.size();
// 返回首部偷和不偷情况中最后金额大的那个
// 注意偷的话还要加上首部的金额，而不偷就不用，相当于加0
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;
// 剩下的代码都是类似的，只不过下标变成了left和right范围！
int n = nums.size();
vector<int> steal(n, 0);
vector<int> nosteal(n, 0);
steal[left] = nums[left];
for(int i = left; i <= right; ++i)
{
steal[i] = nosteal[i-1] + nums[i];
nosteal[i] = max(steal[i-1], nosteal[i-1]);
}
return max(steal[right], nosteal[right]);
}
};4、打家劫舍Ⅲ（medium）
小偷又发现了一个新的可行窃的地区。这个地区只有一个入口，我们称之为 root 。
除了 root 之外，每栋房子有且只有一个“父“房子与之相连。一番侦察之后，聪明的小偷意识到“这个地方的所有房屋的排列类似于一棵二叉树”。 如果 两个直接相连的房子在同一天晚上被打劫 ，房屋将自动报警。
给定二叉树的 root 。返回 在不触动警报的情况下 ，小偷能够盗取的最高金额 。
示例 1:
输入: root = [3,2,3,null,3,null,1]
输出: 7
解释: 小偷一晚能够盗取的最高金额 3 + 3 + 1 = 7示例 2:
输入: root = [3,4,5,1,3,null,1]
输出: 9
解释: 小偷一晚能够盗取的最高金额 4 + 5 = 9提示：
- 树的节点数在
[1, 104]范围内 0 <= Node.val <= 104
解题思路
这道题和前两道题相比，多考察了二叉树的遍历，如果二叉树不是很熟的话，这道题相对来说就比较困难了，其实这种题就叫做树形dp！
下面是状态表示的解析，用图片展示：
接下来就是状态转移方程了，和以前不同的是，我们现在还要结合上图所说的二叉树的后序遍历，也就是先进行后序遍历，然后再配合状态转移方程！如下图所示：
这道题并不涉及初始化的细节问题！
而执行顺序很明显就是后序遍历！
返回值其实就是一个状态表，最后我们返回两种状态对应的最大金额那个即可！
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
class Solution {
public:
int rob(TreeNode* root) {
// dfs返回的数组长度是2
// 第一个元素表示该节点进行偷取，此时的最大金额
// 第二个元素表示该节点不偷取，此时的最大金额
vector<int> dp = dfs(root);
return max(dp[0], dp[1]);
}
vector<int> dfs(TreeNode* cur)
{
if(cur == nullptr)
return {0, 0};
// 采用后序遍历，因为我们想让中间节点最后获得左右节点的最大金额情况并返回
vector<int> leftdp = dfs(cur->left);
vector<int> rightdp = dfs(cur->right);
// 分别考虑当前节点偷和不偷的情况
// 1.如果偷，那么它的左右节点就不能偷了，所以加上它们的不能偷的情况，并且加上当前节点的值
int steal_val = cur->val + leftdp[1] + rightdp[1];
// 2.不偷的话，左右节点可以选择偷和不偷，所以加上它们两种情况的最大金额情况
int nosteal_val = max(leftdp[0], leftdp[1]) + max(rightdp[0], rightdp[1]);
// 最后返回给上层堆栈当前的偷和不偷的金额情况
return {steal_val, nosteal_val};
}
};5、删除并获得点数（medium）
给你一个整数数组 nums ，你可以对它进行一些操作。每次操作中，选择任意一个 nums[i] ，删除它并获得 nums[i] 的点数。之后，你必须删除 所有 等于 nums[i] - 1 和 nums[i] + 1 的元素。
开始你拥有 0 个点数。返回你能通过这些操作获得的最大点数。
示例 1：
输入：nums = [3,4,2]
输出：6
解释：
删除 4 获得 4 个点数，因此 3 也被删除。
之后，删除 2 获得 2 个点数。总共获得 6 个点数。示例 2：
输入：nums = [2,2,3,3,3,4]
输出：9
解释：
删除 3 获得 3 个点数，接着要删除两个 2 和 4 。
之后，再次删除 3 获得 3 个点数，再次删除 3 获得 3 个点数。
总共获得 个点数。 提示：
1 <= nums.length <= 2 * 1041 <= nums[i] <= 104
解题思路
这道题其实直接做的话不好做，因为比较难找规律，但是我们可以将它转化为之前写过的打家劫舍那道题！
为什么要将原数组映射到一个有序且连续的数组中去呢❓❓❓
这是因为原数组就算我们将它排序了，比如图中的原数组，在 4 的前面并不是 3，而是 2，它们之间相差了一定的距离，而如果我们数组中还有其它距离更大的，那么就很难统一这个状态转移方程！
而就算它是连续的，我们也依旧要将其进行排序，才能转化为打家劫舍那种模型去解决，那不如干脆一点，直接将它们映射到有序且连续的数组中去，其中那些缺失的数字，就用 0 来表示，这样子就算状态转移方程加上它们也就是加上 0，也不会有什么影响！
这里只阐述为何要映射到连续数组，而对于状态转移方程和返回值等问题，都是和打家劫舍这道题一模一样的，详细的参考上面，这里就不赘述了！
class Solution {
public:
int deleteAndEarn(vector<int>& nums) {
// 预处理工作，将数组中的值统计到数组中，转化为打家劫舍问题
// 找出最大值
int n = nums.size();
int Max = INT_MIN;
for(int i = 0; i < n; ++i)
{
if(Max < nums[i])
Max = nums[i];
}
vector<int> hash(Max + 1, 0); // 创建0-Max的hash表
for(int i = 0; i < n; ++i)
{
// 将原数组中的数映射到hash表中，但是每次累加的次数，而是这个数的大小
hash[nums[i]] += nums[i];
}
// 下面的步骤就和打家劫舍是差不多的了！
vector<int> del(Max + 1, 0);
vector<int> nodel(Max + 1, 0);
del[0] = hash[0]; // 初始化
for(int i = 1; i <= Max; ++i)
{
del[i] = nodel[i - 1] + hash[i];
nodel[i] = max(del[i - 1], nodel[i - 1]);
}
return max(del[Max], nodel[Max]);
}
};6、粉刷房子（medium）
假如有一排房子，共 n 个，每个房子可以被粉刷成红色、蓝色或者绿色这三种颜色中的一种，你需要粉刷所有的房子并且使其相邻的两个房子颜色不能相同。
当然，因为市场上不同颜色油漆的价格不同，所以房子粉刷成不同颜色的花费成本也是不同的。每个房子粉刷成不同颜色的花费是以一个 n x 3 的正整数矩阵 costs 来表示的。
例如，costs[0][0] 表示第 0 号房子粉刷成红色的成本花费；costs[1][2] 表示第 1 号房子粉刷成绿色的花费，以此类推。
请计算出粉刷完所有房子最少的花费成本。
示例 1：
输入: costs = [[17,2,17],[16,16,5],[14,3,19]]
输出: 10
解释: 将 0 号房子粉刷成蓝色，1 号房子粉刷成绿色，2 号房子粉刷成蓝色。
最少花费: 2 + 5 + 3 = 10。示例 2：
输入: costs = [[7,6,2]]
输出: 2提示:
costs.length == ncosts[i].length == 31 <= n <= 1001 <= costs[i][j] <= 20
注意：本题与主站 256 题相同：https://leetcode-cn.com/problems/paint-house/
解题思路
-
状态表示
-
根据 “经验 + 题目要求”，我们想到以某处为结尾，然后怎么怎么样这种情况。
-
很明显，这道题和之前写的题不太一样的就是这道题其实有三种状态，分别是涂红、蓝、绿的情况：
dp[i][0]表示：粉刷到 i 位置的时候，最后⼀个位置粉刷上「红色」，此时的最小花费dp[i][1]表示：粉刷到 i 位置的时候，最后⼀个位置粉刷上「蓝色」，此时的最小花费dp[i][2]表示：粉刷到 i 位置的时候，最后⼀个位置粉刷上「绿色」，此时的最小花费
-
也就是说我们需要用一个起码三行或者三列的二维数组来表示这三种状态，而 i 下标表示达到第 i 个房子，依照题目给我们的，其实就是三列来表示三种状态，也就是如下图所示：
-
-
状态转移方程
- 以涂红色为例，其它两种情况都是一样的。当我们走到第 i 个房子的时候，题目要求相邻的各自不能涂相同的颜色，那么此时 i - 1 的格子相邻房子就不能涂红色了，只能涂蓝色和绿色，而我们要的是最小花费，所以取涂那两种颜色中的最小花费就行了，记得还要加上当前房子的涂刷费用，就是当前房子的涂红色的最小花费了！可以推出方程如下：
- 对于红色：
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]
- 对于红色：
- 以涂红色为例，其它两种情况都是一样的。当我们走到第 i 个房子的时候，题目要求相邻的各自不能涂相同的颜色，那么此时 i - 1 的格子相邻房子就不能涂红色了，只能涂蓝色和绿色，而我们要的是最小花费，所以取涂那两种颜色中的最小花费就行了，记得还要加上当前房子的涂刷费用，就是当前房子的涂红色的最小花费了！可以推出方程如下：
-
初始化
- 因为这道题我们需要用到 i-1 下标处，而这道题给的范围是从 1 开始的，也就是数组的下标为 0 开始，而有可能只有一个房子，此时访问 i-1 就会越界了，所以这里我们就用之前学过的虚拟位置，也就是将所有位置往后移动一位，然后在首部加上一个虚拟位置，此时我们需要关注两个问题：
- 虚拟位置的初始值，必须保证后面填表的正确
- 因为我们第一个房子希望它的初始值是原来数组中的对应的值，所以虚拟位置置为 0 即可！
- 下标的映射关系
- 这个主要体现在代码中，对题目提供的数组访问的时候，需要注意与我们自己创建的数组的映射关系
- 虚拟位置的初始值，必须保证后面填表的正确
- 因为这道题我们需要用到 i-1 下标处，而这道题给的范围是从 1 开始的，也就是数组的下标为 0 开始，而有可能只有一个房子，此时访问 i-1 就会越界了，所以这里我们就用之前学过的虚拟位置，也就是将所有位置往后移动一位，然后在首部加上一个虚拟位置，此时我们需要关注两个问题：
-
填表顺序
- 很明显就是从左往右，但是对应上图来说，其实是从上到下遍历！
-
返回值
- 返回值就是返回最后一个房子得到的三种涂色中最小花费的那个！
class Solution {
public:
int minCost(vector<vector<int>>& costs) {
int n = costs.size();
vector<vector<int>> dp(n + 1, vector<int>(3, 0)); // n+1行3列，初始值为0（主要是为了虚拟位置）
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];
}
// 返回最后一个房子得到的三种涂色中最小花费的那个
int tmp = min(dp[n][0], dp[n][1]);
return min(tmp, dp[n][2]);
}
};7、买卖股票的最佳时机含冷冻期（medium）
给定一个整数数组prices，其中第 prices[i] 表示第 i 天的股票价格 。
设计一个算法计算出最大利润。在满足以下约束条件下，你可以尽可能地完成更多的交易（多次买卖一支股票）:
- 卖出股票后，你无法在第二天买入股票 (即进入冷冻期，为期 1 天)。
注意：你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。
示例 1:
输入: prices = [1,2,3,0,2]
输出: 3
解释: 对应的交易状态为: [买入, 卖出, 冷冻期, 买入, 卖出]示例 2:
输入: prices = [1]
输出: 0提示：
1 <= prices.length <= 50000 <= prices[i] <= 1000
解题思路
这道题也涉及到多种状态，并且它们关系之间其实比较复杂，我们需要用到所谓的“状态机”帮我们理清一下思路，不过首先我们要先进行状态表示，如下图所示：
接下来我们利用 “状态机”，画出它们之间的关系，简单地说就是谁能到谁，谁不能到谁。然后根据这些状态，获得对应的状态转移方程：
其实取最大值是因为题目要求的是最大利润，那么肯定是取最大值！此外，由 i-1 到 i 的时候自己推导自己，虽说啥也不干，但是可能不干时候的利润比干完还大，所以也要进行比较！
接下来就是初始化问题，因为用到 i-1 处，为了方便这里就不开虚拟位置了，直接就初始化下标为 0 处即可。那么如何初始化呢❓❓❓
- 对于
dp[0][0]来说，表示此刻买入了该处的股票，那么此时利润肯定是负数，也就是dp[0][0] = -price[0]。 - 对于
dp[0][1]来说，表示此刻是可交易状态，那么此刻是没有买入股票的，也因为是第一个位置，所以利润为 0，也就是dp[0][1] = 0。 - 对于
dp[0][2]来说，表示此刻是冷冻期状态，很明显，利润为 0，也就是dp[0][2] = 0。
然后就是填表顺序，从上往下（按照我们状态表示来，这不是固定的），一次性填三个表。
最后就是返回值，我们直接返回最后一行中三个状态的最大值也就是最大利润即可，但更仔细一点会发现，其实我们返回“可交易”和“冷冻期”状态的最大值就行了，因为想一下就知道，此时“买入”状态的话，利润是减少的（花钱买股票当然是减少），所以根本不需要和它们去比，但是如果没有想这么多，直接返回它们三个的最大值也是可以的！
class Solution {
public:
int maxProfit(vector<int>& prices) {
// 创建dp表，这里用n行3列，每列代表一个状态
int n = prices.size();
vector<vector<int>> dp(n, vector<int>(3, 0));
// 初始化，因为上面创建dp的时候已经初始化为0
// 所以只需要初始化“买入”状态即可
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]);
}
};8、买卖股票的最佳时期含手续费（medium）
给定一个整数数组 prices，其中 prices[i]表示第 i 天的股票价格 ；整数 fee 代表了交易股票的手续费用。
你可以无限次地完成交易，但是你每笔交易都需要付手续费。如果你已经购买了一个股票，在卖出它之前你就不能再继续购买股票了。
返回获得利润的最大值。
注意：这里的一笔交易指买入持有并卖出股票的整个过程，每笔交易你只需要为支付一次手续费。
示例 1：
输入：prices = [1, 3, 2, 8, 4, 9], fee = 2
输出：8
解释：能够达到的最大利润:
在此处买入 prices[0] = 1
在此处卖出 prices[3] = 8
在此处买入 prices[4] = 4
在此处卖出 prices[5] = 9
总利润: ((8 - 1) - 2) + ((9 - 4) - 2) = 8示例 2：
输入：prices = [1,3,7,5,10,3], fee = 3
输出：6提示：
1 <= prices.length <= 5 * 1041 <= prices[i] < 5 * 1040 <= fee < 5 * 104
解题思路
一开始这道题我想的太复杂了，在想状态机的时候觉得有三个状态来表示，分别是 “买入”、“卖出”、“什么也不做”，但是在画状态机的时候发现其实这样子画出来的状态很冗余而且比较乱，其实主要原因是以为我们觉得 “买入” 和 “卖出” 这两个状态表示起来不是很明确，所以我建议将其改成 “持有股票” 和 “不持有股票”，对于上一道题同样如此，这样子理解对这道题的状态会更加清晰！
下面以图片形式给出状态表示和状态转移方程的解析：
对于初始化，因为状态转移方程需要用到 i-1 位置处，所以我们需要初始化一下下标为 0 处防止越界，因为我们有两个状态，所以下面来讨论一下它们两个对应的初始化问题：
- 对于 ”持有股票“ 状态，也就是
dp[0][0]，因为它表示当前持有股票，很明显由于是第一次出发，所以它要拿到当前位置的股票，所以就要减去当前位置的股票，也就是dp[0][0] = -prices[i] - 对于 ”不持有股票“ 状态，也就是
dp[0][1]，很明显，就让它表示啥也不干，也不持有股票，所以就是dp[0][1] = 0
对于填表顺序，很明显就是从左往右，一次填两个表。
对于返回值，其实我们可以返回这两个状态的最大值那个，但是因为最后 ”持有股票“ 状态没卖出去股票，所以其实按道理来说当前的利润是要比 ”不持有股票“，相当于卖出了股票后的利润要小的，所以直接返回 dp[n-1][1] 即可！
class Solution {
public:
int maxProfit(vector<int>& prices, int fee) {
// 创建dp表
int n = prices.size();
vector<vector<int>> dp(n, vector<int>(2, 0));
// 初始化
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][0] + prices[i] - fee);
}
// 返回值
return dp[n - 1][1];
}
};9、买卖股票的最佳时机III（hard）
给定一个数组，它的第 i 个元素是一支给定的股票在第 i 天的价格。设计一个算法来计算你所能获取的最大利润。你最多可以完成 两笔 交易。
注意：你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。
示例 1:
输入：prices = [3,3,5,0,0,3,1,4]
输出：6
解释：在第 4 天（股票价格 = 0）的时候买入，在第 6 天（股票价格 = 3）的时候卖出，这笔交易所能获得利润 = 3-0 = 3 。
随后，在第 7 天（股票价格 = 1）的时候买入，在第 8 天 （股票价格 = 4）的时候卖出，这笔交易所能获得利润 = 4-1 = 3 。示例 2：
输入：prices = [1,2,3,4,5]
输出：4
解释：在第 1 天（股票价格 = 1）的时候买入，在第 5 天 （股票价格 = 5）的时候卖出, 这笔交易所能获得利润 = 5-1 = 4 。
注意你不能在第 1 天和第 2 天接连购买股票，之后再将它们卖出。
因为这样属于同时参与了多笔交易，你必须在再次购买前出售掉之前的股票。示例 3：
输入：prices = [7,6,4,3,1]
输出：0
解释：在这个情况下, 没有交易完成, 所以最大利润为 0。示例 4：
输入：prices = [1]
输出：0提示：
1 <= prices.length <= 1050 <= prices[i] <= 105
解题思路
这道题比较难的点在于多了一个限制条件：最多交易不超过两次。也就是我们需要多给一个维度去表示当前的交易次数，因为交易次数不一定越多利润就越高，可能交易次数为零的时候利润最高也是有可能的，所以得多一个维度来表示当前的交易次数！
但是如果像之前那样子我们用一个二维数组去表示两种状态，现在又多加了一个维度去表示交易次数，那就变成了三维数组，那么就比较麻烦，所以我们这里就用两个数组分别表示两种状态，每个数组都是二维数组，具体看下图解析：
除此之外，我们在状态表示中用了 j 来表示交易次数的下标，为什么不具体到这道题的 0、1、2 呢❓❓❓
其实是因为用 j 来表示下标的话，更加有通用性，特别是体现在下一题，其实下一题就是在这道题的基础之上变形的，只不过将最多交易两次变成了交易 k 次，那么这样子表示的话其实通用性是很大的，我们下面在讲状态转移方程的时候，其实没必要去限制在两次的范围之内，只需要最后返回的时候找到交易次数在两次以内的即可！
接下来就是状态转移方程的解析，具体参考下图：
上面的状态转移方程并不完全正确，因为还要结合一下初始化的情况来进行修改，下面是初始化问题的解析：
至于为什么不是初始化为 INT_MIN 而是 INT_MIN 的一半❓❓❓这个问题其实很好回答！
这是因为我们的状态转移方程中涉及到了对 [i - 1, j] 或者 [i - 1, j - 1] 访问的时候，如果使用的是 INT_MIN，也就是最小的整形，这个时候还得加上或者减去 prices[i]，当然这里的加上并不会造成问题，这道题最致命的是这个减去 prices[i] 的操作，因为 INT_MIN 减去一个整数，那就惨了，溢出了变成了一个很大的数字，那么此时取到的值就变成了一个很大的值，这就不对了！
所以一般在解题的时候，涉及到对最值的加减法的时候，我们都会将其初始化为最值的一半比如 INT 类型最值的一半：0x3f3f3f3f 或者 -0x3f3f3f3f，因为这个数值也是非常大的，题目给的数据基本不会超过它，并且也不会有哪个数字说会让其溢出，当然要结合题目要求，在这道题中是没问题的！
填表顺序，从上往下，从左往右填三个次数的利润，一次填两个表也就是两种状态！
返回值，其实不用考虑持有股票的那个状态，因为它不卖出股票，肯定比卖出股票利润小呀，所以返回不持有股票状态中几次交易次数中最大利润即可！
class Solution {
public:
int maxProfit(vector<int>& prices) {
const int MIN = 0x3f3f3f3f; // int类型最值的一半
// 创建dp表，这里两种状态分为两个表：持有股票、不持有股票
int n = prices.size();
vector<vector<int>> hold(n, vector<int>(3, -MIN));
vector<vector<int>> unhold(n, vector<int>(3, -MIN));
// 初始化
hold[0][0] = -prices[0];
unhold[0][0] = 0;
// 填表，从上往下，从左往右填三个次数的利润，一次填两个表也就是两种状态
for(int i = 1; i < n; ++i)
{
for(int j = 0; j < 3; ++j)
{
hold[i][j] = max(hold[i - 1][j], unhold[i - 1][j] - prices[i]);
unhold[i][j] = unhold[i - 1][j];
if(j > 0)
unhold[i][j] = max(unhold[i][j], hold[i - 1][j - 1] + prices[i]);
}
}
// 返回值，其实不用考虑持有股票的那个状态，因为它不卖出股票，肯定比卖出股票利润小呀
// 所以返回不持有股票状态中几次交易次数中最大利润即可
int res = 0; // 不需要赋值为INT_MIN，因为当利润为负了，那么不如不玩股票，也就是利润最大为0
for(int i = 0; i < 3; ++i)
res = max(res, unhold[n - 1][i]);
return res;
}
};10、 买卖股票的最佳时机IV（hard）
给定一个整数数组 prices ，它的第 i 个元素 prices[i] 是一支给定的股票在第 i 天的价格，和一个整型 k 。
设计一个算法来计算你所能获取的最大利润。你最多可以完成 k 笔交易。也就是说，你最多可以买 k 次，卖 k 次。
注意：你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。
示例 1：
输入：k = 2, prices = [2,4,1]
输出：2
解释：在第 1 天 (股票价格 = 2) 的时候买入，在第 2 天 (股票价格 = 4) 的时候卖出，这笔交易所能获得利润 = 4-2 = 2 。示例 2：
输入：k = 2, prices = [3,2,6,5,0,3]
输出：7
解释：在第 2 天 (股票价格 = 2) 的时候买入，在第 3 天 (股票价格 = 6) 的时候卖出, 这笔交易所能获得利润 = 6-2 = 4 。
随后，在第 5 天 (股票价格 = 0) 的时候买入，在第 6 天 (股票价格 = 3) 的时候卖出, 这笔交易所能获得利润 = 3-0 = 3 。提示：
0 <= k <= 1000 <= prices.length <= 10000 <= prices[i] <= 1000
解题思路：
要是上面那道题解决了，这道题简直就是小 case！为什么这么说呢，因为我们在写上一道题的时候，其实就已经有了 k 种交易次数的思想，现在只不过将上一题的两种交易次数变成了 k 种而已！
其实就是改变代码中的开辟空间大小和遍历范围的大小，注意是 k+1，而不是 k，因为交易次数包括 0 次，所以要算上！
优化
这道题其实是可以优化的，因为我们知道，要想得到一次完整的交易，肯定是需要两天的，一天用来买入，一天用来卖出，所以总共的交易次数最多为 n/2 次对吧，但是有没有可能 k 它是大于 n/2 的，那么我们就做了不必要的遍历，所以我们可以取 k 和 n/2 的最小值作为最大的交易次数！
下面代码中只贴上和上一题的主要区别的注释，其它注释省略了，具体可以参考上一题的注释：
class Solution {
public:
int maxProfit(int k, vector<int>& prices) {
const int MIN = 0x3f3f3f3f;
int n = prices.size();
k = min(k, n/2); // 进行可能的优化
// 创建dp表
vector<vector<int>> hold(n, vector<int>(k + 1, -MIN)); // 注意是k+1种次数，因为包括交易0次
vector<vector<int>> unhold(n, vector<int>(k + 1, -MIN)); // 注意是k+1种次数，因为包括交易0次
// 初始化
hold[0][0] = -prices[0];
unhold[0][0] = 0;
// 填表
for(int i = 1; i < n; ++i)
{
for(int j = 0; j < k + 1; ++j) // 注意是k+1种次数，因为包括交易0次
{
hold[i][j] = max(hold[i - 1][j], unhold[i - 1][j] - prices[i]);
unhold[i][j] = unhold[i - 1][j];
if(j > 0)
unhold[i][j] = max(unhold[i][j], hold[i - 1][j - 1] + prices[i]);
}
}
// 返回值
int res = 0;
for(int i = 0; i < k + 1; ++i) // 注意是k+1种次数，因为包括交易0次
res = max(res, unhold[n - 1][i]);
return res;
}
};