51工具盒子状态机DP就是考虑到当前时刻、位置等，有可能处于有限种情形中的其中一种
比如说当前位置的房子涂了什么颜色、当前时间的股票处于卖出还是买入的状态、当前删除到的序列是以0还是以1结尾、当前位置是放了还是没有放置东西、当前位置是正还是负
把这些情况分开来转移可以使得转移的思路更加清晰明了，类比成当前位置 i 的一个状态 j 能够由前面位置 i-1 的指定状态 k 转移得到！！！
1.粉刷房子问题 {#1-粉刷房子问题}
1.1 剑指 Offer II 091. 粉刷房子 {#1-1-剑指-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])
|---------------------------------------------|----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------|
| 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])); } } |
1.2 LC1473. 粉刷房子 III {#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)
|------------------------------------------------------------------------------------------------------------------------------------------------------------------|----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------|
| 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) { // 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-6种股票问题}
2.1 LC121. 买卖股票的最佳时机 {#2-1-LC121-买卖股票的最佳时机}
|------------------------------------------------------------------------------------------|-------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------|
| 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) { /* 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 {#2-2-LC122-买卖股票的最佳时机-II}
|------------------------------------------------------------------------------------------|---------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------|
| 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) { /* dp解法: 1.状态定义:dp[i][0]代表第i天(操作后)不持有股票的最大身价,dp[i][1]代表第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 {#2-3-LC123-买卖股票的最佳时机-III}
|---------------------------------------------------------------------------------|---------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------|
| 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) { /* 总体思路:第i天有5个阶段:0.还没买 1.第一次买入后 2.第一次抛售后 3.第二次买入后 4.第二次抛售后 1.状态定义:dp[i][0]为第i天处于阶段0的最大身价;dp[i][1]为第i天处于阶段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 {#2-4-LC188-买卖股票的最佳时机-IV}
|------------------------------------------------------------------------------------------------------------------------------------|-------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------|
| 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) { /* 总体思路:与买卖股票的最佳时机 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. 最佳买卖股票时机含冷冻期 {#2-5-LC309-最佳买卖股票时机含冷冻期}
|---------------------------------------------------------------------------------------------------------------|--------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------|
| 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) { /* 总体思路:与最佳买卖股票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][4]-prices[i]) =max(dp[i-1][5]-prices[i],dp[i-1][4]-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. 买卖股票的最佳时机含手续费 {#2-6-LC714-买卖股票的最佳时机含手续费}
|---------------------------------------------------------------------------|----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------|
| 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) { /* 与股票买卖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. 将字符串翻转到单调递增 {#3-LC926-将字符串翻转到单调递增}
|------------------------------------------------------------------------------------------------------|-------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------|
| 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) { /* 动态规划: 翻转后的单调递增字符串可能的情形有: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. 统计放置房子的方式数 {#4-LC2320-统计放置房子的方式数}
|------------------------------------------------------------------------------------------------------|-------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------|
| 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) { /* 状态机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 {#5-LC552-学生出勤记录-II}
|------------------------------------------------------------------------------------------------------------------------------------------|--------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------|
| 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) { /* 动态规划: 按 总出勤 计，学生缺勤（'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; } } |
