状态机DP就是考虑到当前时刻、位置等，有可能处于有限种情形中的其中一种
比如说当前位置的房子涂了什么颜色、当前时间的股票处于卖出还是买入的状态、当前删除到的序列是以0还是以1结尾、当前位置是放了还是没有放置东西、当前位置是正还是负
把这些情况分开来转移可以使得转移的思路更加清晰明了，类比成当前位置 i 的一个状态 j 能够由前面位置 i-1 的指定状态 k 转移得到！！！
1.粉刷房子问题
分状态的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])
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
| 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]));
}
}
|
状态机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)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
| 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) {
dp[0][houses[0]][1] = 0;
} else {
for (int j = 1; j <= n; j++) {
dp[0][j][1] = cost[0][j - 1];
}
}
for (int i = 1; i < m; i++) {
for (int j = 1; j <= n; j++) {
for (int k = 1; k <= target; k++) {
if (houses[i] == 0) {
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) {
dp[i][j][k] = Math.min(dp[i][j][k], cost[i][j - 1] + dp[i - 1][jj][k - 1]);
}
}
} else {
if (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) {
dp[i][j][k] = Math.min(dp[i][j][k], dp[i - 1][jj][k - 1]);
}
}
}
}
}
}
}
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种股票问题
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
| class Solution {
public int maxProfit(int[] prices) {
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];
}
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
| class Solution {
public int maxProfit(int[] prices) {
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];
}
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
| class Solution {
public int maxProfit(int[] prices) {
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]);
}
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
| class Solution {
public int maxProfit(int k, int[] prices) {
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++) {
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;
}
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
| class Solution {
public int maxProfit(int[] prices) {
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]));
}
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
| class Solution {
public int maxProfit(int[] prices, int fee) {
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];
}
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
| class Solution {
public int minFlipsMonoIncr(String s) {
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]);
}
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
| class Solution {
public int countHousePlacements(int n) {
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;
}
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
| class Solution {
public int checkRecord(int n) {
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;
}
long[] sum = new long[n + 1];
sum[0] = 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;
}
long res = sum[n];
for (int i = 1; i <= n; i++) {
res = (res + (sum[i - 1] * sum[n - i]) % MOD) % MOD;
}
return (int) res;
}
}
|
