状态机DP就是考虑到当前时刻、位置等,有可能处于有限种情形中的其中一种

比如说当前位置的房子涂了什么颜色、当前时间的股票处于卖出还是买入的状态、当前删除到的序列是以0还是以1结尾、当前位置是放了还是没有放置东西、当前位置是正还是负

把这些情况分开来转移可以使得转移的思路更加清晰明了,类比成当前位置 i 的一个状态 j 能够由前面位置 i-1 的指定状态 k 转移得到!!!

1.粉刷房子问题

1.1 LC123.剑指 Offer II 091. 粉刷房子

分状态的DP问题(序列DP):

1.状态定义:dp[i][0],dp[i][1],dp[i][2]分别为粉刷房子[0,i],且房子i的颜色粉刷为红色/蓝色/绿色所花费的最低费用

为什么还要带一个后缀?因为粉刷第i间房子可能的状态本身有3种!

如果混在一起讨论非常复杂,分开讨论可以根据前面的状态分开转移就非常方便

类似于股票问题->考虑第i天且第i天处于卖出还是买入状态方便转移!

2.状态转移:由于相邻的两个房子颜色不能相同,因此根据dp[i-1][j]的状态分类转移即可

​ 2.1 dp[i][0]可以由dp[i-1][1]与dp[i-1][2]加上cost[i][0]取最小值转移

​ 2.2 dp[i][1]可以由dp[i-1][0]与dp[i-1][2]加上cost[i][1]取最小值转移

​ 2.3 dp[i][2]可以由dp[i-1][0]与dp[i-1][1]加上cost[i][2]取最小值转移

意义就是我这间房子涂了颜色0,那么只能由前面涂了不是颜色0的进行转移且取最小值

3.初始化:初始化dp[0][0]=cost[0][0],dp[0][1]=cost[0][1],dp[0][2]=cost[0][2]

4.遍历顺序:i正序,j无所谓

5.返回形式:涂到最后一间房子最小费用不知道是以哪种颜色结尾的,可以取最小值min(dp[n-1][0],dp[n-1][1],dp[n-1][2])

class Solution {
public int minCost(int[][] costs) {
int n = costs.length;
int[][] dp = new int[n][3];
dp[0][0] = costs[0][0];
dp[0][1] = costs[0][1];
dp[0][2] = costs[0][2];
for (int i = 1; i < n; i++) {
dp[i][0] = costs[i][0] + Math.min(dp[i - 1][1], dp[i - 1][2]);
dp[i][1] = costs[i][1] + Math.min(dp[i - 1][0], dp[i - 1][2]);
dp[i][2] = costs[i][2] + Math.min(dp[i - 1][0], dp[i - 1][1]);
}
return Math.min(dp[n - 1][0], Math.min(dp[n - 1][1], dp[n - 1][2]));
}
}

1.2 LC1473. 粉刷房子 III

状态机DP问题(参考剑指OfferII.91 粉刷房子):

其实与之前那道粉刷房子的也很类似,不过这里更加复杂一点就是要考虑形成的街区数目,同时有的房子已经涂了色

我们前面一道题是考虑到两个dp维度:房子位置i,第i间房子的颜色j

要同时考虑形成的街区数目(独立),此时必须增加一个dp的维度k,表示当前形成的街区数目

同时要对已经涂了色的情况进行分类讨论转移

1.状态定义: dp[i][j][k]为考虑对房子[0,i]进行涂色,且房子i(i∈[0,m-1])颜色被涂为颜色j(j∈[1,n]),且涂完之后就形成k(k∈[1,target])个街区的最小花费

2.状态转移: 我们以house[i]是否为0进行分类讨

​ 2.1 house[i]==0 表示房子i还没有被涂色,选择任意颜色j∈[1,n]对房子i进行涂色,涂的具体颜色会影响街区的数目

​ dp[i][j][k]=cost[i][j-1]+min(dp[i-1][j][k],dp[i-1][j’][k-1]) 其中j’为≠j的集合(颜色不同街区数+1)

​ 注意细节:合法的dp[i-1][jj][?]状态才能转移

​ 2.2 house[i]!=0 表示房子i已经被涂色,此时只能对dp[i][house[i]][k]进行转移,其他dp[i][j’][?]无法转移仍为INF

​ dp[i][houses[i]][k]=0+min(dp[i-1][houses[i]][k],dp[i-1][j’][k-1]) 其中j’为≠houses[i]的集合(颜色不同街区数+1)

3.初始化: 首先全部初始化为INF表示没有转移

​ 当houses[0]==0时,dp[0][j][1]=cost[0][j-1] -> 要涂色

​ 当houses[0]!=0时,dp[0][houses[0]][1]=0 -> 不用涂色

4.遍历顺序: 显然i正序,j无所谓,k正序

5.返回形式: 最后返回min(dp[m-1][j][target]),j∈[1,n] 若扔没有转移则返回-1

时间复杂度:O((mn)^2) 空间复杂度:O(n*m^2)

public int minCost(int[] houses, int[][] cost, int m, int n, int target) {
int INF = 0x3f3f3f3f; // 哨兵
int[][][] dp = new int[m][n + 1][target + 1];
// 初始化
for (int i = 0; i < m; i++) {
for (int j = 1; j <= n; j++) {
Arrays.fill(dp[i][j], INF);
}
}
if (houses[0] != 0) { // 1.首个房子不用涂色
dp[0][houses[0]][1] = 0;
} else { // 2.首个房子要涂色,费用最小就是直接涂,且只能形成一个街区
for (int j = 1; j <= n; j++) {
dp[0][j][1] = cost[0][j - 1];
}
}
// 遍历dp的每个状态
// i∈[1,m-1]
for (int i = 1; i < m; i++) {
// j∈[1,n]
for (int j = 1; j <= n; j++) {
// k∈[1,target]
for (int k = 1; k <= target; k++) {
if (houses[i] == 0) { // 1.houses[i]要涂色
// 遍历所有可能的houses[i-1]的颜色进行转移
for (int jj = 1; jj <= n; jj++) {
// 细节:只有有效的状态才能进行转移
if (jj == j && dp[i - 1][jj][k] != INF) { // 与前面颜色相同,街区数目不变
dp[i][j][k] = Math.min(dp[i][j][k], cost[i][j - 1] + dp[i - 1][jj][k]);
} else if (jj != j && dp[i - 1][jj][k - 1] != INF) { // 与前面颜色不同,街区数目+1
dp[i][j][k] = Math.min(dp[i][j][k], cost[i][j - 1] + dp[i - 1][jj][k - 1]);
}
}
} else { // 2.houses[i]已经被涂色
if (j == houses[i]) { // 只能转移j==houses[i]的状态
for (int jj = 1; jj <= n; jj++) {
if (jj == j && dp[i - 1][jj][k] != INF) { // 与前面颜色相同,街区数目不变(且不用花费)
dp[i][j][k] = Math.min(dp[i][j][k], dp[i - 1][jj][k]);
} else if (jj != j && dp[i - 1][jj][k - 1] != INF) { // 与前面颜色不同,街区数目+1(且不用花费)
dp[i][j][k] = Math.min(dp[i][j][k], dp[i - 1][jj][k - 1]);
}
}
}
}
}
}
}
// 结果为min(dp[m-1][j][target]),j∈[1,n] 不为INF部分的最小值
int res = INF;
for (int j = 1; j <= n; j++) {
res = Math.min(res, dp[m - 1][j][target]);
}
return res == INF ? -1 : res;
}

2.6种股票问题

2.1 LC121. 买卖股票的最佳时机

class Solution {
public int maxProfit(int[] prices) {
/*
dp五部曲:主要根据每天持有与不持有股票的状态进行转移
1.状态定义:dp[i][0]代表第i天(操作后)不持有股票的最大身价,dp[i][0]代表第i天(操作后)持有股票的最大身价
2.状态转移:
2.1 dp[i][0]第i天不持有股票
1.当天卖了:dp[i-1][1]+prices[i]
2.之前就卖了:dp[i-1][0]
3.还没买:0 (可以忽略)
取最大值转移值dp[i][0]
2.2 dp[i][1]第i天持有股票
1.当天入手:-prices[i]
2.之前就入手了:dp[i-1][1]
取最大值转移值dp[i][1]
3.初始化:第0天的情况->dp[0][0]=0,dp[0][1]=-prices[0]
4.遍历顺序:i正序,j无所谓
5.返回形式:最后一天肯定是卖出股票的身价大->dp[len-1][0];
*/
int len = prices.length;
int[][] dp = new int[len][2];
dp[0][0] = 0;
dp[0][1] = -prices[0];
for (int i = 1; i < len; i++) {
dp[i][0] = Math.max(dp[i - 1][1] + prices[i], dp[i - 1][0]);
dp[i][1] = Math.max(-prices[i], dp[i - 1][1]);
}
return dp[len - 1][0];
}
}

2.2 LC122. 买卖股票的最佳时机 II

class Solution {
public int maxProfit(int[] prices) {
/*
dp解法:
1.状态定义:dp[i][0]代表第i天(操作后)不持有股票的最大身价,dp[i][0]代表第i天(操作后)持有股票的最大身价
2.状态转移:
2.1 dp[i][0]第i天不持有股票
1.当天卖了:dp[i-1][1]+prices[i]
2.之前就卖了:dp[i-1][0]
3.还没买:0 (可以忽略)
取最大值转移值dp[i][0]
2.2 dp[i][1]第i天持有股票
1.当天入手:dp[i-1][0]-prices[i] (区别在此,之前不持有股票可能已经交易过几轮了)
2.之前就入手了:dp[i-1][1]
取最大值转移值dp[i][1]
3.初始化:第0天的情况->dp[0][0]=0,dp[0][1]=-prices[0]
4.遍历顺序:i正序,j无所谓
5.返回形式:最后一天肯定是卖出股票的身价大->dp[len-1][0]
*/
int len = prices.length;
int[][] dp = new int[len][2];
dp[0][0] = 0;
dp[0][1] = -prices[0];
for (int i = 1; i < len; i++) {
dp[i][0] = Math.max(dp[i - 1][1] + prices[i], dp[i - 1][0]);
dp[i][1] = Math.max(dp[i - 1][0] - prices[i], dp[i - 1][1]);
}
return dp[len - 1][0];
}
}

2.3 LC123. 买卖股票的最佳时机 III

class Solution {
public int maxProfit(int[] prices) {
/*
总体思路:第i天有5个阶段:0.还没买 1.第一次买入后 2.第一次抛售后 3.第二次迈买入后 4.第二次抛售后
1.状态定义:dp[i][0]为处于的阶段0最大身价;dp[i][1]为处于阶段1最大身价;....
2.状态转移:
2.1 阶段0身价恒为0
2.2 阶段1有两种情况:当天第一次买和之前第一次买了,取大的值:max(dp[i-1][0]-prices[i],dp[i-1][1])
2.3 阶段2有两种情况:当天第一次卖和之前第一次卖了,取大的值:max(dp[i-1][1]+prices[i],dp[i-1][2])
2.3 阶段3有两种情况:当天第二次买和之前第二次买了,取大的值:max(dp[i-1][2]-prices[i],dp[i-1][3])
2.3 阶段4有两种情况:当天第二次卖和之前第二次卖了,取大的值:max(dp[i-1][3]+prices[i],dp[i-1][4])
3.初始化:dp[0][0]=0,dp[0][1]=-prices[0],dp[0][2]=0,dp[0][3]=-prices[0],dp[0][4]=0
4.遍历顺序:i正序,j无所谓
5.返回形式:第一次卖出与第二次卖出取最大值:max(dp[len-1][2],dp[len-1][4])
*/
int len = prices.length;
int[][] dp = new int[len][5];
dp[0][1] = dp[0][3] = -prices[0];
for (int i = 1; i < len; i++) {
dp[i][1] = Math.max(dp[i - 1][0] - prices[i], dp[i - 1][1]);
dp[i][2] = Math.max(dp[i - 1][1] + prices[i], dp[i - 1][2]);
dp[i][3] = Math.max(dp[i - 1][2] - prices[i], dp[i - 1][3]);
dp[i][4] = Math.max(dp[i - 1][3] + prices[i], dp[i - 1][4]);
}
return Math.max(dp[len - 1][2], dp[len - 1][4]);
}
}

2.4 LC188. 买卖股票的最佳时机 IV

class Solution {
public int maxProfit(int k, int[] prices) {
/*
总体思路:与买卖股票的最佳时机 III 接近,将买卖股票的阶段分为第x次买入和第x次卖出
状态0:处于还没买入过的阶段
状态1:处于第1次买入后的阶段
状态2:处于第1次卖出后的阶段
状态3:处于第2次买入后的阶段
状态4:处于第2次卖出后的阶段
...以此类推,dp[i][j]中的i代表的是处于第i天,j代表的当前股票的状态
j为奇数时,表示处于第j/2+1次买入股票阶段;j为偶数时,表示处于第j/2次卖出股票阶段
1.状态定义:dp[i][j]代表第i天处于的状态j时的最大收益
2.状态转移:参考状态1与2可以推导出后面的
2.0 还没买入过的阶段(j=0)->恒为0(直接初始化为0就可以完成求解)
2.1 第1次买入后的阶段(j=1):今天刚买与之前就买了取较大值->max(dp[i-1][0]-prices[i],dp[i-1][1])
2.2 第1次卖出后的阶段(j=2):今天刚卖与之前就卖了取较大值->max(dp[i-1][1]+prices[i],dp[i-1][2])
...以此类推,那么dp[i][j]可以以j为依据分为两种情况进行转移计算:
j为奇数时->dp[i][j]=max(dp[i-1][j-1]-prices[i],dp[i-1][j])
j为偶数时->dp[i][j]=max(dp[i-1][j-1]+prices[i],dp[i-1][j])
3.初始化:j奇数表示买入的状态->dp[0][j]=-prices[0],j奇偶表示卖出的状态->dp[0][j]=0
4.遍历顺序:i正序,j无所谓
5.返回形式:返回dp[len-1][j]其中j为偶数的最大值(卖出时身价比持有时大)
*/
if (prices == null || prices.length == 0 || k == 0) return 0;
int len = prices.length;
int[][] dp = new int[len][2 * k + 1];
// 初始化
for (int j = 1; j <= 2 * k; j += 2) {
dp[0][j] = -prices[0];
}
for (int i = 1; i < len; i++) {
// 统计j为奇数的情况:奇数+1就是偶数
for (int j = 1; j <= 2 * k; j += 2) {
dp[i][j] = Math.max(dp[i - 1][j - 1] - prices[i], dp[i - 1][j]);
dp[i][j + 1] = Math.max(dp[i - 1][j] + prices[i], dp[i - 1][j + 1]);
}
}
int max = 0;
for (int j = 2; j <= 2 * k; j += 2) {
max = Math.max(max, dp[len - 1][j]);
}
return max;
}
}

2.5 LC309. 最佳买卖股票时机含冷冻期

class Solution {
public int maxProfit(int[] prices) {
/*
总体思路:与最佳买卖股票II比较类似,可以无限次交易但是含有冷冻期
一共有以下6个状态:
状态0:当前还没操作股票
状态1:今天刚买入
状态2:之前就买入了
状态3:今天刚卖出
状态4:处于冷冻期
状态5:之前卖出且过了冷冻期
1.状态定义:dp[i][j]表示第i天处于状态j的最大收益
2.状态转移:
2.0 dp[i][0]=0
2.1 dp[i][1]=max(dp[i-1][0]-prices[i],dp[i-1][5]-prices[i],dp[i-1][3]-prices[i])
=max(dp[i-1][5]-prices[i],dp[i-1][3]-prices[i])
2.2 dp[i][2]=max(dp[i-1][1],dp[i-1][2])
2.3 dp[i][3]=max(dp[i-1][2]+prices[i],dp[i-1][1]+prices[i])
2.4 dp[i][4]=dp[i-1][3]
2.5 dp[i][5]=max(dp[i-1][4],dp[i-1][5])
3.初始化:dp[0][0]=0,dp[0][1]=-prices[0],dp[0][2]=-prices[0],dp[0][3]=dp[0][4]=dp[0][5]=0
4.遍历顺序:i正序,j无所谓
5.返回形式:返回max(dp[len-1][3],dp[len][4],dp[len-1][5])
*/
int len = prices.length;
int[][] dp = new int[len][6];
dp[0][1] = dp[0][2] = -prices[0];
for (int i = 1; i < len; i++) {
dp[i][1] = Math.max(dp[i - 1][5] - prices[i], dp[i - 1][4] - prices[i]);
dp[i][2] = Math.max(dp[i - 1][1], dp[i - 1][2]);
dp[i][3] = Math.max(dp[i - 1][2] + prices[i], dp[i - 1][1] + prices[i]);
dp[i][4] = dp[i - 1][3];
dp[i][5] = Math.max(dp[i - 1][4], dp[i - 1][5]);
}
return Math.max(dp[len - 1][3], Math.max(dp[len - 1][4], dp[len - 1][5]));
}
}

2.6 LC714. 买卖股票的最佳时机含手续费

class Solution {
public int maxProfit(int[] prices, int fee) {
/*
与股票买卖II十分类似,唯一的不同就是要支付手续费,可以看做卖出的时候股票价格减少fee
一共有2种状态:(其中没操作股票归纳到情况1)
状态0:持有股票
状态1:不持有股票
1.状态定义:dp[i][j]代表的第i天处于状态j时的最大身价
2.状态转移:
2.0 持有股票,可能今天刚买或者之前就买了:dp[i][0]=max(dp[i-1][1]-prices[i],dp[i-1][0])
2.1 不持有股票,可能今天刚卖或者之前就卖了:dp[i][1]=max(dp[i-1][1],dp[i-1][0]+prices[i]-fee)
3.初始化:初始化dp[0][0]=-prices[0],dp[0][1]=0
4.遍历顺序:i正序,j任意
5.返回形式:返回dp[len-1][1]
*/
int len = prices.length;
int[][] dp = new int[len][2];
dp[0][0] = -prices[0];
for (int i = 1; i < len; i++) {
dp[i][0] = Math.max(dp[i - 1][1] - prices[i], dp[i - 1][0]);
dp[i][1] = Math.max(dp[i - 1][1], dp[i - 1][0] + prices[i] - fee);
}
return dp[len - 1][1];
}
}

3.LC926. 将字符串翻转到单调递增

class Solution {
public int minFlipsMonoIncr(String s) {
/*
动态规划:
翻转后的单调递增字符串可能的情形有:000...000 000...111 111...111
归结起来就是两种情形:以0结尾和以1结尾 分开来考虑转移会更加明确
1.状态定义:f[i][0]为考虑s[0,i]翻转后为以0结尾的s[0,i]为递增序列最少翻转次数
f[i][1]为考虑s[0,i]翻转后为以1结尾的s[0,i]为递增序列最少翻转次数
2.状态转移:要求f[i][0]与f[i][1]就要看s[i]
2.1 s[i]==0时 f[i][0]=f[i-1][0] f[i][1]=min(f[i-1][1],f[i-1][0])+1
2.2 s[i]==1时 f[i][1]=min(f[i-1][0],f[i-1][1]) f[i][0]=f[i-1][0]+1
3.初始化:f[0][0]=s[0]==0?0:1 f[0][1]=s[0]==1?0:1
4.遍历顺序:i正序
5.返回形式:返回min(f[n-1][0],f[n-1][1]) 最后被翻转成0或者1结尾都有可能使得翻转次数最少
时间复杂度:O(N)
*/
int n = s.length();
char[] chs = s.toCharArray();
int[][] f = new int[n][2];
f[0][0] = chs[0] == '0' ? 0 : 1;
f[0][1] = chs[0] == '1' ? 0 : 1;
for (int i = 1; i < n; i++) {
if (chs[i] == '0') {
f[i][0] = f[i - 1][0];
f[i][1] = Math.min(f[i - 1][1], f[i - 1][0]) + 1;
} else {
f[i][0] = f[i - 1][0] + 1;
f[i][1] = Math.min(f[i - 1][0], f[i - 1][1]);
}
}
return Math.min(f[n - 1][0], f[n - 1][1]);
}

}

4.LC2320. 统计放置房子的方式数

class Solution {
public int countHousePlacements(int n) {
/*
状态机DP问题(有更加简单的做法,这里为了演示状态机DP):
1.状态定义:
1.1 f[i][0]为考虑两边[0,i]的地方i位置上下都不放置房子的方案数
1.2 f[i][1]为考虑两边[0,i]的地方i位置只放上面的地方
1.3 f[i][2]为考虑两边[0,i]的地方i位置只放下面的地方
1.4 f[i][3]为考虑两边[0,i]的地方i位置上下都放置房子的方案数
2.状态转移:考虑i位置一共有4种状态,根据实际转移即可
f[i][0]=f[i-1][3]+f[i-1][2]+f[i-1][1]+f[i-1][0]
f[i][1]=f[i-1][2]+f[i-1][0]
f[i][2]=f[i-1][1]+f[i-1][0]
f[i][3]=f[i-1][0]
3.初始化:f[0][0]=f[0][1]=f[0][2]=f[0][3]=1
4.遍历顺序:i正序
5.返回形式:最后4种情形加起来就是答案sum(f[n-1][j])
*/
int MOD = (int) 1e9 + 7;
long[][] f = new long[n][4];
Arrays.fill(f[0], 1);
for (int i = 1; i < n; i++) {
f[i][0] = (f[i - 1][3] + f[i - 1][2] + f[i - 1][1] + f[i - 1][0]) % MOD;
f[i][1] = (f[i - 1][2] + f[i - 1][0]) % MOD;
f[i][2] = (f[i - 1][1] + f[i - 1][0]) % MOD;
f[i][3] = (f[i - 1][0]) % MOD;
}
long res = 0;
for (long ff : f[n - 1]) {
res = (res + ff) % MOD;
}
return (int) res;
}
}

5.LC552. 学生出勤记录 II

class Solution {
public int checkRecord(int n) {
/*
动态规划:
按 总出勤 计,学生缺勤('A')严格 少于两天。
那么可以将情况分为两种:0天或者1天A
其中,1天的可以枚举A出现的天数,然后两边通过乘法原理进行求解次数
0天的可以通过动态规划进行求解,因为只有L与P两种状态,合法情况为最多两个连续的L
1.状态定义:由于第i天(从1开始)的选择被前两天i-1与i-2限制了,因此会多出两个维度f[i][pre][cur]
因此定义f[i][0][0]为第i-1与i天选择为LL的情形数,f[i][0][1]为第i-1与i天选择为LP的情形数
f[i][1][0]为第i-1与i天选择为PL的情形数,f[i][1][1]为第i-1与i天选择为PP的情形数
2.状态转移:显然f[i][0][0]=f[i-1][1][0],f[i][0][1]=f[i-1][0][0]+f[i-1][1][0]
f[i][1][0]=f[i-1][0][1]+f[i-1][1][1],f[i][1][1]=f[i-1][1][1]+f[i-1][0][1]
3.初始化:f[2][0][0]=1,f[2][1][0]=1,f[2][0][1]=1,f[2][1][1]=1
4.遍历顺序:i正序,其余任意
5.返回形式:∑f[n][pre][cur]+有1个A的情形数
*/
int MOD = (int) 1e9 + 7;
if (n == 1) return 3;
long[][][] f = new long[n + 1][2][2];
f[2][0][0] = 1;
f[2][1][0] = 1;
f[2][0][1] = 1;
f[2][1][1] = 1;
for (int i = 3; i <= n; i++) {
f[i][0][0] = f[i - 1][1][0];
f[i][0][1] = (f[i - 1][0][0] + f[i - 1][1][0]) % MOD;
f[i][1][0] = (f[i - 1][0][1] + f[i - 1][1][1]) % MOD;
f[i][1][1] = (f[i - 1][1][1] + f[i - 1][0][1]) % MOD;
}
// sum[i]表示长度为i天数不包含A的合法情形数
long[] sum = new long[n + 1];
sum[0] = 1; // 没有天数视为1
sum[1] = 2;
for (int i = 2; i <= n; i++) {
sum[i] = (f[i][0][0] + f[i][0][1] + f[i][1][0] + f[i][1][1]) % MOD;
}
// System.out.println(Arrays.toString(sum));
long res = sum[n];
// 统计带A的合法情形数,其中i为A出现的位置
for (int i = 1; i <= n; i++) {
res = (res + (sum[i - 1] * sum[n - i]) % MOD) % MOD;
}
return (int) res;
}
}