动态规划虽然说有一定难度，主要是找到状态转移的公式，但是也依然是有些规律可以找寻的。
现在来说一下有限状态机，我们知道动态规划一般是用来求最值的情况，那么就会存在一类题型，在某一个位置或者时刻可以选择多种状态，求最值
举个例子，比如生活中常见的 买东西，顾客遍历所有的商品，对每一个商品都可以选择买还是不买两种状态，求怎样在有限的钱下花的最值。
或者说我在任意时间都可以选择买入还是卖出股票，怎么获得最大利益。
这些还是只有一两个状态，当然也可以有多个状态，比如说进程的状态，在一个状态只有由其他几个状态转换，来限制转换的条件
首先我们来看一个题目：
假期
由于业绩优秀，公司给小Q放了 n 天的假，身为工作狂的小Q打算在在假期中工作、锻炼或者休息。他有个奇怪的习惯：不会连续两天工作或锻炼。只有当公司营业时，小Q才能去工作，只有当健身房营业时，小Q才能去健身，小Q一天只能干一件事。给出假期中公司，健身房的营业情况，求小Q最少需要休息几天。
输入描述:
第一行一个整数 n(1\leq n\leq 100000)n(1≤n≤100000) 表示放假天数
第二行 n 个数 每个数为0或1,第 i 个数表示公司在第 i 天是否营业
第三行 n 个数 每个数为0或1,第 i 个数表示健身房在第 i 天是否营业
（1为营业 0为不营业）
4
1 1 0 0
0 1 1 0
2
根据题目，小Q 可以有三种状态，休息，工作，锻炼
工作 <-> 锻炼
\ /
休息
思路使用有限状态机0表示休息， 1锻炼， 2工作
其次题目中还限制了那一天可以工作那一天锻炼，最少休息的天数，可以转化为是最大锻炼和工作的天数
int[][] dp=new int[n+1][3];
当然求最小就是先赋值为n，然后每次减一
代码如下
public static void main(String[] args) {
Scanner in=new Scanner(System.in);
int n=in.nextInt();
int[] gym=new int[n];
int[] work=new int[n];
for(int i=0;i<n;i++) {
work[i]=in.nextInt();
}
for(int i=0;i<n;i++) {
gym[i]=in.nextInt();
}
//开始操作数据
int[][] dp=new int[n+1][3]; // 0：休息 1：锻炼 2：工作
for(int i=1;i<=n;i++) {
if(gym[i-1]==1) { // 可以锻炼
dp[i][1]=Math.max(dp[i-1][0], dp[i-1][2])+1;
}
if(work[i-1]==1) { // 可以工作
dp[i][2]=Math.max(dp[i-1][0], dp[i-1][1])+1;
}
dp[i][0]=Math.max(dp[i-1][0], Math.max(dp[i-1][1], dp[i-1][2]));
}
int res=Math.max(dp[n][0], Math.max(dp[n][1], dp[n][2]));
System.out.println(n-res);
}
也可以将代码简化为只有两种状态，工作，健身，使昨天的值直接赋值今天代表休息
public static void main(String[] args) {
Scanner in=new Scanner(System.in);
int n=in.nextInt();
int[] gym=new int[n];
int[] work=new int[n];
for(int i=0;i<n;i++) {
work[i]=in.nextInt();
}
for(int i=0;i<n;i++) {
gym[i]=in.nextInt();
}
// 求最大不休息天数，健身，工作，休息可以作为中间态省略
int[][] dp=new int[n+1][2];
for(int i=1;i<=n;i++) {
// 工作 , 前天健身和前天工作的最大值，这样休息包含在其中 dp[i-1][0]
dp[i][0] = Math.max(dp[i-1][1] + work[i-1],dp[i-1][0]);
// 健身
dp[i][1] = Math.max(dp[i-1][0] + gym[i-1],dp[i-1][1]);
}
int res=Math.max(dp[n][0], dp[n][1]);
System.out.println(n-res);
}
这里的状态只和上一次的状态有关，任然可以进行优化
另一个比较经典的例子是股票的买入卖出
股票有限状态机
给定一个数组，它的第 i 个元素是一支给定股票第 i 天的价格。
如果你最多只允许完成一笔交易（即买入和卖出一支股票一次），设计一个算法来计算你所能获取的最大利润。
注意：你不能在买入股票前卖出股票。
示例 1:
输入: [7,1,5,3,6,4]
输出: 5
解释: 在第 2 天（股票价格 = 1）的时候买入，在第 5 天（股票价格 = 6）的时候卖出，最大利润 = 6-1 = 5 。
注意利润不能是 7-1 = 6, 因为卖出价格需要大于买入价格；同时，你不能在买入前卖出股票。
示例 2:
输入: [7,6,4,3,1]
输出: 0
解释: 在这种情况下, 没有交易完成, 所以最大利润为 0。
public int maxProfit(int[] prices) {
if(prices == null || prices.length == 0){
return 0;
}
int[][] dp = new int[prices.length][2];
// 0 代表卖出 或者不动， 1 代表买入；
dp[0][0] = 0;
dp[0][1] = -prices[0];
for(int i=1;i<prices.length;i++){
// 买入不动或者卖出
dp[i][0] = Math.max(dp[i-1][0],dp[i-1][1] + prices[i]);
dp[i][1] = Math.max(dp[i-1][1],-prices[i]);
}
return dp[prices.length-1][0];
}
但是当前的状态之和上一个状态有关可以再进行优化
public int maxProfit(int[] prices) {
if(prices == null || prices.length == 0){
return 0;
}
// 0 代表卖出 或者不动， 1 代表买入；
int sell = 0;
int buy = -prices[0];
for(int i=1;i<prices.length;i++){
// 买入不动或者卖出
sell = Math.max(sell,buy + prices[i]);
buy = Math.max(buy,-prices[i]);
}
return sell;
}
122. 买卖股票的最佳时机 II
给定一个数组，它的第 i 个元素是一支给定股票第 i 天的价格。
设计一个算法来计算你所能获取的最大利润。你可以尽可能地完成更多的交易（多次买卖一支股票）。
注意：你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。
给定一个数组，它的第 i 个元素是一支给定股票第 i 天的价格。
设计一个算法来计算你所能获取的最大利润。你可以尽可能地完成更多的交易（多次买卖一支股票）。
注意：你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。
这里 可以无限次的买入卖出
// 这里允许多次买卖
public int maxProfit(int[] prices) {
int[][] dp = new int[prices.length+1][2];
dp[0][0] = 0;
dp[0][1] = Integer.MIN_VALUE;
for (int i = 1;i<prices.length+1;i++){
dp[i][0] = Math.max(dp[i-1][0],dp[i-1][1] + prices[i-1]);
// 在这里加上可以从上次的基础上买入即可
dp[i][1] = Math.max(dp[i-1][1],dp[i-1][0]-prices[i-1]);
}
return dp[prices.length][0];
}
当然任然可以优化
123. 买卖股票的最佳时机 III
给定一个数组，它的第 i 个元素是一支给定的股票在第 i 天的价格。
设计一个算法来计算你所能获取的最大利润。你最多可以完成 两笔 交易。
注意: 你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。
示例 1:
输入: [3,3,5,0,0,3,1,4]
输出: 6
解释: 在第 4 天（股票价格 = 0）的时候买入，在第 6 天（股票价格 = 3）的时候卖出，这笔交易所能获得利润 = 3-0 = 3 。
随后，在第 7 天（股票价格 = 1）的时候买入，在第 8 天 （股票价格 = 4）的时候卖出，这笔交易所能获得利润 = 4-1 = 3 。
示例 2:
输入: [1,2,3,4,5]
输出: 4
解释: 在第 1 天（股票价格 = 1）的时候买入，在第 5 天 （股票价格 = 5）的时候卖出, 这笔交易所能获得利润 = 5-1 = 4 。
注意你不能在第 1 天和第 2 天接连购买股票，之后再将它们卖出。
因为这样属于同时参与了多笔交易，你必须在再次购买前出售掉之前的股票。
指定次数的买卖就需要在多加一个状态进行维护
public int maxProfit(int[] prices,int k) {
int[][][] dp = new int[prices.length+1][k+1][2];
dp[0][k][0] = 0;
dp[0][k][1] = Integer.MIN_VALUE;
for (int i = 1;i<prices.length+1;i++){
for(int j=k;j>=1;j--) {
dp[i][j][0] = Math.max(dp[i - 1][j][0], dp[i - 1][j][1] + prices[i - 1]);
dp[i][j][1] = Math.max(dp[i - 1][j][1], dp[i - 1][j-1][0] - prices[i - 1]);
}
}
return dp[prices.length][k][0];
}
