【算法提高：动态规划】1.4 状态机模型 TODO

例题列表

1049. 大盗阿福（其实就是打家劫舍）

https://www.acwing.com/activity/content/problem/content/1287/

就是 打家劫舍 那道题。

对当前的房间选择 抢 或者 不抢。

import java.io.BufferedInputStream;
import java.util.*;public class Main {public static void main(String[] args) {Scanner sin = new Scanner(new BufferedInputStream(System.in));int t = sin.nextInt();while (t-- != 0) {int n = sin.nextInt();int second = 0, pre = sin.nextInt();for (int i = 1; i < n; ++i) {int temp = pre;pre = Math.max(pre, second + sin.nextInt());second = temp;}System.out.println(pre);}}
}

1057. 股票买卖 IV（k笔交易）

https://www.acwing.com/problem/content/1059/

dp 数组多开一维表示第几笔交易就好了。

import java.io.BufferedInputStream;
import java.util.*;public class Main {public static void main(String[] args) {Scanner sin = new Scanner(new BufferedInputStream(System.in));int n = sin.nextInt(), k = sin.nextInt();int[] prices = new int[n];for (int i = 0; i < n; ++i) prices[i] = sin.nextInt();int[][] buy = new int[n][k], sell = new int[n][k];Arrays.fill(buy[0], -prices[0]);for (int i = 1; i < n; ++i) {buy[i][0] = Math.max(buy[i - 1][0], -prices[i]);sell[i][0] = Math.max(sell[i - 1][0], buy[i - 1][0] + prices[i]);for (int j = 1; j < k; ++j) {buy[i][j] = Math.max(buy[i - 1][j], sell[i - 1][j - 1] - prices[i]);sell[i][j] = Math.max(sell[i - 1][j], buy[i - 1][j] + prices[i]);}}System.out.println(sell[n - 1][k - 1]);}
}

1058. 股票买卖 V（冷冻期）

https://www.acwing.com/problem/content/1060/

限制 buy[i] 只能从 sell[i - 2] 转移过来就好了。

import java.io.BufferedInputStream;
import java.util.*;public class Main {public static void main(String[] args) {Scanner sin = new Scanner(new BufferedInputStream(System.in));int n = sin.nextInt();int[] buy = new int[n], sell = new int[n], prices = new int[n];for (int i = 0; i < n; ++i) prices[i] = sin.nextInt();buy[0] = -prices[0];buy[1] = Math.max(buy[0], -prices[1]);sell[1] = Math.max(sell[0], buy[0] + prices[1]);for (int i = 2; i < n; ++i) {buy[i] = Math.max(sell[i - 2] - prices[i], buy[i - 1]);sell[i] = Math.max(buy[i - 1] + prices[i], sell[i - 1]);}System.out.println(sell[n - 1]);}
}

1052. 设计密码⭐⭐⭐🚹🚹🚹（TODO）

https://www.acwing.com/activity/content/problem/content/1290/

|T| + 1 个状态自动机。

在这里插入代码片

1053. 修复DNA🚹🚹🚹🚹🚹（TODO）

https://www.acwing.com/activity/content/problem/content/1291/

在这里插入代码片