动态规划（简单多状态 dp 问题 1.按摩师 2.打家劫舍 II 3. 删除并获得点数 4.粉刷房子 5.买卖股票的最佳时机（全系列））
- 面试题 17.16. 按摩师
- 213. 打家劫舍 II
- 740. 删除并获得点数
- LCR 091. 粉刷房子 （原：剑指 Offer II 091. 粉刷房子）
- 309. 买卖股票的最佳时机含冷冻期
- 714. 买卖股票的最佳时机含手续费
- 123. 买卖股票的最佳时机 III
- 188. 买卖股票的最佳时机 IV
1.按摩师
题目分析：
我们在题目中可以了解到按摩师不能按摩相邻两个请求。于是：
| 1 | 2 | 3 | 1 | |
当我们选 1 时，2号就不能选了，可选3号和4号，同理，我们再选3号，就不能选4号
当我们选 2 时，1号和3号就不能选了，可选4号
于是我们得最大预约时长就是1号和3号；
2.讲解算法原理
1.状态表示：
dp[i] 表示为到达 i 的位置时，此时的最长预约时间；
| 0 | 1 | ........ | i-1 | i |
此时我们到达i是有两种结果
1. 选择 i 下表的预约时长
2. 不选择 i 下表的预约时长
分析到这我们发现，只定义一种状态表示不了两种结果；
于是我们需要定义两种状态来表示两种结果；即
f[i] 表示:选择到i位置的时候，nums[i] 必选此时的最长预约时长
g[i] 表示:选择到i位置的时候，nums[i] 不选，此时的最长预约时长
2.状态转移方程
| 0 | 1 | ........ | i-1 | i |
| × | √ |
1.选择 i 下表的预约时长时
则我们前面 f [i -1]的状态就只一种，就是不选，但是我们要加上nums的值，所以
f[i] = g[i - 1] + nums[i];
2.不选择 i 下表的预约时长时
| 0 | 1 | ........ | i-1 | i |
| × |
则我们前面 g [i -1]的状态就有两种
1. 不选 时：g[i -1]
2 . 选时：f[i -1]
我们 g [ i ] 就表示为到达（g [i -1]和 f [i - 1])的最大值即可：
g[i] = Math.max(g[i -1],f[i -1]);
3.初始化:
当我们选择第一个时，此时 f [ 0 ] = nums[0];
当我们不选择第一个时，此时 g [ 0 ] = 0;
4.填表顺序：
从左往右，两个表一起填
5.返回值：
返回选和不选时的最大值即可：
return Math.max(f[n - 1],g[n - 1]);
3.编写代码
2. 打家劫舍 II
题目分析：
我们可以看出 打家劫舍 II 和按摩师大差不差，就是这些房子串起来了。于是我们直接步入正题。
2.讲解算法原理
分析：
dp[i] 表示为到达 i 的位置时，此时的偷窃房子达到的最大金额；
因为是环形的所以我们转化成两个线性的“打家劫舍1通过分类讨论，将环形的问题，
| 0 | 1 | 2 | 3 | ......... | i -3 | i -2 | i - 1 | i |
那么怎么转化成两个线性呢？
就是看我们第一个房子和最后一个房子的状态
1.当我们第一个房子偷时：此时我们发现1号房子和 i 号房子都偷不了
2.当我们最后一个房子偷时：此时我们发现0号房子和 i -1 号房子都偷不了
于是我们可以看出只有四个房子受到影响，那么我们就可以单独拿来讨论，即为第一个线性：
rob（1，i - 1）
剩下不受影响的房子我们就可以转化成另一个线性：
rob（2，i - 2）
当我们转化为两个线性dp后，就和按摩师的算法原理一样了
1.状态表示：
dp[i] 表示为到达 i 的位置时，此时的最长预约时间；
| 0 | 1 | ........ | i-1 | i |
此时我们到达i是有两种结果
1. 选择 i 下表的预约时长
2. 不选择 i 下表的预约时长
分析到这我们发现，只定义一种状态表示不了两种结果；
于是我们需要定义两种状态来表示两种结果；即
f[i] 表示:选择到i位置的时候，nums[i] 必选此时的最长预约时长
g[i] 表示:选择到i位置的时候，nums[i] 不选，此时的最长预约时长
2.状态转移方程
| 0 | 1 | ........ | i-1 | i |
| × | √ |
1.选择 i 下表的预约时长时
则我们前面 f [i -1]的状态就只一种，就是不选，但是我们要加上nums的值，所以
f[i] = g[i - 1] + nums[i];
2.不选择 i 下表的预约时长时
| 0 | 1 | ........ | i-1 | i |
| × |
则我们前面 g [i -1]的状态就有两种
1. 不选 时：g[i -1]
2 . 选时：f[i -1]
我们 g [ i ] 就表示为到达（g [i -1]和 f [i - 1])的最大值即可：
g[i] = Math.max(g[i -1],f[i -1]);
3.初始化:
当我们选择第一个时，此时 f [ 0 ] = nums[0];
当我们不选择第一个时，此时 g [ 0 ] = 0;
4.填表顺序：
从左往右，两个表一起填
5.返回值：
返回选和不选时的最大值即可：
return Math.max(f[n - 1],g[n - 1]);
3.编写代码
3. 删除并获得点数
题目分析：
我们从题目中可以看出，如果选择num[i] = 3的值话， 那么 2 的值和4的值就不能选了，于是乎我们的第一个实例就为 4 + 2 =6；
2.讲解算法原理
分析：
| 2 | 2 | 3 | 3 | 3 | 4 |
我们看上述的例子会发现相同的数都可以相加在一起，但是选择num[i] = 3的值,那么 2 的值和4的值就不能选了
于是我们可以在创建一个数组去统计所有相同数字的和，并将数组中的数，统计到 arr 中。然后在 arr 中，做一次“打家劫舍”问题即可，此时我们得arr数组就为：
| 1 | 2 | 3 | 4 |
| 0 | 4 | 9 | 4 |
我们这样便利一下就好了：
for(int x : nums) arr[x]+=x;
1.状态表示：
dp[i] 表示为到达 i 的位置时，此时的最长预约时间；
| 0 | 1 | ........ | i-1 | i |
此时我们到达i是有两种结果
1. 选择 i 下表的预约时长
2. 不选择 i 下表的预约时长
分析到这我们发现，只定义一种状态表示不了两种结果；
于是我们需要定义两种状态来表示两种结果；即
f[i] 表示:选择到i位置的时候，nums[i] 必选此时的最长预约时长
g[i] 表示:选择到i位置的时候，nums[i] 不选，此时的最长预约时长
2.状态转移方程
| 0 | 1 | ........ | i-1 | i |
| × | √ |
1.选择 i 下表的预约时长时
则我们前面 f [i -1]的状态就只一种，就是不选，但是我们要加上nums的值，所以
f[i] = g[i - 1] + nums[i];
2.不选择 i 下表的预约时长时
| 0 | 1 | ........ | i-1 | i |
| × |
则我们前面 g [i -1]的状态就有两种
1. 不选 时：g[i -1]
2 . 选时：f[i -1]
我们 g [ i ] 就表示为到达（g [i -1]和 f [i - 1])的最大值即可：
g[i] = Math.max(g[i -1],f[i -1]);
3.初始化:
当我们选择第一个时，此时 f [ 0 ] = nums[0];
当我们不选择第一个时，此时 g [ 0 ] = 0;
4.填表顺序：
从左往右，两个表一起填
5.返回值：
返回选和不选时的最大值即可：
return Math.max(f[n - 1],g[n - 1]);
3.编写代码
4.粉刷房子
题目分析：
| 红 | 蓝 | 绿 |
| 17 | 2 | 17 |
| 16 | 16 | 5 |
| 14 | 3 | 19 |
我们从以上表中就能看出我们将 0 号房子粉刷成蓝色，1 号房子粉刷成绿色，2 号房子粉刷成蓝色。花销最少，并且你需要粉刷所有的房子并且使其相邻的两个房子颜色不能相同。
2.讲解算法原理
1.状态表示：
| 0 | 1 | ........ | n - 1 | n |
当我们粉刷最后一个时，我们会有三种状态表示：
dp[i][0]表示:粉刷到i位置的时候，最后一个位置粉刷上 红色,此时的最小花费
dp[i][1]表示:粉刷到i位置的时候，最后一个位置粉刷上 蓝色此时的最小花费
dp[i][2]表示:粉刷到i位置的时候，最后一个位置粉刷上 绿色，此时的最小花费
2.状态转移方程
1.粉刷到 i 位置的时候，最后一个位置粉刷上红色时，那么我们在 i - 1位置时只能粉刷为 蓝色和绿色的最小花费。
dp[i][0] = Math.min(dp[i - 1][1],dp[i - 1][2])+costs[i - 1][0];
2.粉刷到 i 位置的时候，最后一个位置粉刷上蓝色时，那么我们在 i - 1位置时只能粉刷为 红色和绿色的最小花费。
dp[i][1] = Math.min(dp[i - 1][0],dp[i - 1][2])+costs[i - 1][1];
3.粉刷到 i 位置的时候，最后一个位置粉刷上绿色时，那么我们在 i - 1位置时只能粉刷为 蓝色和红色的最小花费。
dp[i][2] = Math.min(dp[i - 1][1],dp[i - 1][0])+costs[i - 1][2];
3.初始化:
1.虚拟节点里面的值，要保证后续填表是正确的
2.下标的映射关系
4.填表顺序：
从左往右，两个表一起填
5.返回值：
返回粉刷 （红色，蓝色，绿色）房子的最小值即可：
return Math.min(dp[n][0],Math.min(dp[n][1],dp[n][2]));
3.编写代码
5. 买卖股票的最佳时机含冷冻期
题目分析：
我们从题目中可以看出卖出股票后，你无法在第二天买入股票 (即冷冻期为 1 天)。你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。
于是我们分析案例可得：
| 1 | 2 | 3 | 0 | 2 |
| 买入 | 卖出 | 冷冻期 | 买入 | 卖出 |
2.讲解算法原理
1.状态表示：
| 0 | 1 | ........ | n - 1 | n |
当我们讨论最后一个时，我们会有三种状态表示：
dp[i][0]表示:第i天结束之后，处于“买入”状态，此时的最大利润
dp[i][1]表示:第i天结束之后，处于“可交易”状态，此时的最大利润
dp[i][2]表示:第i天结束之后，处于““冷冻期”状态，此时的最大利润
2.状态转移方程
我们可以先画一个状态机来表示所有状态：（箭头的末端为前一天的状态）
1.当我们前一天（n - 1）为买入股票时（此时手里是有股票的）我们可以考虑三种情况
1-1.卖出股票进入冷冻期，此时我们手里有.卖出股票的钱 + price[i - 1]
1-2 这一天我们也可以啥也不干
1-3 因为此时我们手里是有股票的，所以不考虑卖出股票这种状态。
2.当我们前一天（n - 1）为冷冻期时（此时手里是没股票的）我们可以考虑三种情况
2-1 因为此时我们处于冷冻期，购买不了股票，所以不考虑买入股票这种状态。
2-2 因为此时我们手里是没有股票的，所以不考虑卖出股票这种状态。
2-3 所以我们只能啥也不干
3.当我们前一天（n - 1）为可交易时（此时手里是没股票的）我们可以考虑三种情况
3-1.买入股票，此时我们要买入股票 所以要 - price[i - 1]（股票的价格）
3-2 这一天我们也可以啥也不干
3-3 因为我们没有卖出股票进入冷冻期，所以不考虑冷冻期这种状态。
由以上分析我们得出第n天的状态
当位买入”状态‘’时，我们可以啥也不干，或者由前一天的可交易状态购买股票的最大值：
dp[i][0] = Math.max(dp[i - 1][0],dp[i - 1][1] - prices[i]);
当位可交易”状态‘’时，我们可以啥也不干，或者由前一天的冷冻期状态啥也不干进入可交易状态：
dp[i][1] = Math.max(dp[i - 1][1],dp[i - 1][2]);
当位冷冻期”状态‘’时，我们可以啥也不干，或者由前一天的买入股票状态去卖出股票的最大值：
dp[i][2] = dp[i - 1][0] + prices[i];
3.初始化:
因为我们dp[i][0]表示:买入”状态所以
dp[0][0] = - prices[i];
其他两种状态的收入均为0：
dp[0][1] = dp[0][2] = 0;
4. 填表顺序
从左往右填写，一次填写三个表
5.返回值
返回三种状态 （冷冻期，可交易，买入）的最大值即可：
因为当处于买入状态时（手里是有股票），没卖出去所以不可能为最大值。
所以我们返回剩下两种状态即可：
return Math.max(dp[n-1][1],dp[n - 1][2]);
3.编写代码
6.买卖股票的最佳时机含手续费
题目分析：
你可以无限次地完成交易，但是你每笔交易都需要付手续费。如果你已经购买了一个股票，在卖出它之前你就不能再继续购买股票了。
返回获得利润的最大值。
注意：这里的一笔交易指买入持有并卖出股票的整个过程，每笔交易你只需要为支付一次手续费。能够达到的最大利润:
示例1：
| 1 | 3 | 2 | 8 | 4 | 9 |
在此处买入 prices[0] = 1
在此处卖出 prices[3] = 8
在此处买入 prices[4] = 4
在此处卖出 prices[5] = 9
总利润: ((8 - 1) - 2) + ((9 - 4) - 2) = 8
2.讲解算法原理
1.状态表示：
| 0 | 1 | ........ | n - 1 | n |
当我们讨论最后一个时，我们会有三种状态表示：
dp[i][0]表示:第i天结束之后，处于“买入”状态，此时的最大利润
dp[i][1]表示:第i天结束之后，处于“卖出”状态，此时的最大利润
2.状态转移方程
我们可以先画一个状态机来表示所有状态：（箭头的末端为前一天的状态）
1.当我们前一天（n - 1）为买入股票时（此时手里是有股票的）我们可以考虑两种情况
1-1.卖出股票，此时我们手里有卖出股票的钱 + price[i - 1]
1-2 这一天我们也可以啥也不干
2.当我们前一天（n - 1）为卖出股票时（此时手里是没股票的）我们可以考虑两种情况
2-1 因为此时我们此时手里是没股票，所以考虑买入股票这种状态 - price[i - 1]
2-2这一天我们也可以啥也不干
由以上分析我们得出第n天的状态
当位‘’买入”状态时，我们可以啥也不干，或者由前一天的状态‘’卖出股票‘’购买股票的最大值：
dp[i][0] = Math.max(dp[i - 1][0],dp[i - 1][1] - prices[i]);
当位‘’卖出股票”状态‘时，我们可以啥也不干，或者由前一天的买入股票状态’卖出股票的最大值，但要注意我们是有手续费的：
dp[i][1] = Math.max(dp[i - 1][1],dp[i-1][0] + prices[i] -fee );
3.初始化:
因为我们dp[i][0]表示:买入”状态所以
dp[0][0] = - prices[i];
其他一种状态的收入均为0：
dp[0][1] = 0;
4. 填表顺序
从左往右填写，一次填写两个表
5.返回值
返回两种状态 （卖出，买入）的最大值即可：
因为当处于买入状态时（手里是有股票），没卖出去所以不可能为最大值。
所以我们返回剩下一种状态即可：
return dp[n - 1][1];
3.编写代码
7.买卖股票的最佳时机 III
题目分析：
它的第 i 个元素是一支给定的股票在第 i 天的价格。
设计一个算法来计算你所能获取的最大利润。你最多可以完成 两笔 交易。
注意：你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。
2.讲解算法原理
1.状态表示：
dp[i] 表示:第i天结束之后，所能获得的最大利润
f[i][j] 表示:第i天结束之后，完成了j次交易,此时处于"买入"状态下的，最大利润
g[i][j] 表示:第i天结束之后，完成了j次交易，!此时处于“卖出"状态下的，最大利润
2.状态转移方程
我们可以先画一个状态机来表示所有状态：（箭头的末端为前一天的状态）
1.当我们前一天（n - 1）为买入股票时（此时手里是有股票的）我们可以考虑两种情况
1-1.卖出股票，此时我们手里有卖出股票的钱 + price[i - 1]
1-2 这一天我们也可以啥也不干
2.当我们前一天（n - 1）为卖出股票时（此时手里是没股票的）我们可以考虑两种情况
2-1 因为此时我们此时手里是没股票，所以考虑买入股票这种状态 - price[i - 1]
2-2这一天我们也可以啥也不干
由以上分析我们得出第n天的状态
当位‘’买入”状态时，我们可以啥也不干，或者由前一天的状态‘’卖出股票‘’购买股票的最大值：
f[i][j] = Math.max(f[i - 1][j],g[i - 1][j] - prices[i]);
当位‘’卖出股票”状态‘时，我们可以啥也不干，或者由前一天的买入股票状态’卖出股票的最大值但是我们卖出时的次数要减1，于是就有了两种情况：
1.啥也不干 g[i][j] = g[i - 1][j - 1];
2.当票的次数减为0，此时g下标的j就会发生数组越界情况，所以我们需要做一下判断来保证数组不越界
if(j >= 1) g[i][j] = Math.max(g[i][j],f[i - 1][j - 1] + prices[i]);
3.初始化:
因为我们定义了两个数组所以要对他们进行讨论：
| 第0次 | 第1次 | 第2次 |
| -p[0] | -0x3f3f3f3f | -0x3f3f3f3f |
| 第0次 | 第1次 | 第2次 |
| 0 | -0x3f3f3f3f | -0x3f3f3f3f |
因为我们所求购买股票的最大值所以不能让后两天的情况去影响我们前两天的值，于是我们把后两天的状态都定义为最小的负值即可，但又怕爆int 所以我们定义为int INF = 0x3f3f3f3f;最大值的一半即可
4. 填表顺序
从上往下填写每一行
每一行从左往右，两个表一起填
5.返回值
y表的最后行里面的最大值
int res = 0;
for(int j =0; j < 3;j++) res = Math.max(res,g[n - 1][j]);
return res;
3.编写代码
8.买卖股票的最佳时机 IV
题目分析：
给你一个整数数组 prices 和一个整数 k ，其中 prices[i] 是某支给定的股票在第 i 天的价格。
设计一个算法来计算你所能获取的最大利润。你最多可以完成 k 笔交易。也就是说，你最多可以买 k 次，卖 k 次。
注意：你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。
2.讲解算法原理
1.状态表示：
dp[i] 表示:第i天结束之后，所能获得的最大利润
f[i][j] 表示:第i天结束之后，完成了k次交易,此时处于"买入"状态下的，最大利润
g[i][j] 表示:第i天结束之后，完成了k次交易，!此时处于“卖出"状态下的，最大利润
2.状态转移方程
初始k的值（代码优化）: 因为我们是有买入股票和卖出股票两种状态，所以我们k值是不会超过数组除2的（无论k值是有多大），所以我们仅需去他俩的最小值即可
k = Math.min(k,n/2);
我们可以先画一个状态机来表示所有状态：（箭头的末端为前一天的状态）
1.当我们前一天（n - 1）为买入股票时（此时手里是有股票的）我们可以考虑两种情况
1-1.卖出股票，此时我们手里有卖出股票的钱 + price[i - 1]
1-2 这一天我们也可以啥也不干
2.当我们前一天（n - 1）为卖出股票时（此时手里是没股票的）我们可以考虑两种情况
2-1 因为此时我们此时手里是没股票，所以考虑买入股票这种状态 - price[i - 1]
2-2这一天我们也可以啥也不干
由以上分析我们得出第n天的状态
当位‘’买入”状态时，我们可以啥也不干，或者由前一天的状态‘’卖出股票‘’购买股票的最大值：
f[i][j] = Math.max(f[i - 1][j],g[i - 1][j] - prices[i]);
当位‘’卖出股票”状态‘时，我们可以啥也不干，或者由前一天的买入股票状态’卖出股票的最大值但是我们卖出时的次数要减1，于是就有了两种情况：
1.啥也不干 g[i][j] = g[i - 1][j - 1];
2.当票的次数减为0，此时g下标的j就会发生数组越界情况，所以我们需要做一下判断来保证数组不越界
if(j >= 1) g[i][j] = Math.max(g[i][j],f[i - 1][j - 1] + prices[i]);
3.初始化:
因为我们定义了两个数组所以要对他们进行讨论：
| 第0次 | 第1次 | 第2次 | ........ | 第k-1次 | 第k次 |
| -p[0] | -0x3f3f3f3f | -0x3f3f3f3f | -0x3f3f3f3f | -0x3f3f3f3f | |
| 第0次 | 第1次 | 第2次 | ........ | 第k-1次 | 第k次 |
| 0 | -0x3f3f3f3f | -0x3f3f3f3f | -0x3f3f3f3f | -0x3f3f3f3f | |
因为我们所求购买股票的最大值所以不能让后两天的情况去影响我们前两天的值，于是我们把后两天的状态都定义为最小的负值即可，但又怕爆int 所以我们定义为int INF = 0x3f3f3f3f;最大值的一半即可
4. 填表顺序
从上往下填写每一行
每一行从左往右，两个表一起填
5.返回值
y表的最后行里面的最大值
int res = 0;
for(int j =0; j < 3;j++) res = Math.max(res,g[n - 1][j]);
return res;
3.编写代码
