本題的鏈接是：假期
題目描述
由于業(yè)績(jī)優(yōu)秀胆数，公司給小Q放了 n 天的假怒允，身為工作狂的小Q打算在在假期中工作砰嘁、鍛煉或者休息淑蔚。他有個(gè)奇怪的習(xí)慣：不會(huì)連續(xù)兩天工作或鍛煉市殷。只有當(dāng)公司營(yíng)業(yè)時(shí)，小Q才能去工作刹衫，只有當(dāng)健身房營(yíng)業(yè)時(shí)醋寝，小Q才能去健身，小Q一天只能干一件事绪妹。給出假期中公司，健身房的營(yíng)業(yè)情況柿究，求小Q最少需要休息幾天邮旷。
輸入描述:
一個(gè)整數(shù)，表示小Q休息的最少天數(shù)
輸入例子1:
4
1 1 0 0
0 1 1 0
輸出例子1:
2
例子說明1:
當(dāng)小Q處于位置3時(shí)蝇摸，他可以向前看到位置2,1處的樓婶肩，向后看到位置4,6處的樓，加上第3棟小Q可以在第一天工作貌夕，第二天或第三天健身律歼，小Q最少休息2天
解題思路-維特比算法
從題目可以知道，小Q的狀態(tài)只有工作啡专，健身险毁，休息三種狀態(tài)，我們可以用dp[i][0]、dp[i][1]畔况、dp[i][2]分別表示小Q第i天在工作鲸鹦，健身，休息的時(shí)候跷跪，他在1~i天有最多有多少天不休息馋嗜。三種狀態(tài)可以用到維特比算法以相互轉(zhuǎn)換：
dp[i][0] = max(dp[i-1][1],dp[i-1][2]) + 1
dp[i][1] = max(dp[i-1][0],dp[i-1][2]) + 1
dp[i][2] = max(dp[i-1][0],dp[i-1][1],dp[i-1][2])
代碼
package niuke.tencent;
import java.util.Scanner;
public class jiaqi {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int n = scanner.nextInt();
int []work = new int[n], gym = new int[n];
for(int i=0;i<n;i++){
work[i] = scanner.nextInt();
}
for(int i=0;i<n;i++){
gym[i] = scanner.nextInt();
}
System.out.println(xiuXi(work,gym));
}
public static int xiuXi(int[] work,int[] gym){
int length = work.length;
// 分別表示：工作健身休息
int[][] dp = new int[length+1][3];
dp[0][0] = dp[0][1] = dp[0][2] = 0;
for (int i = 1; i <=length ; i++) {
// 可以工作
if(work[i-1] == 1)
dp[i][0] = Math.max(dp[i-1][1],dp[i-1][2]) + 1;
// 可以健身
if(gym[i-1] == 1)
dp[i][1]=Math.max(dp[i-1][0],dp[i-1][2]) + 1;
dp[i][2]=Math.max(dp[i-1][0],Math.max(dp[i-1][1],dp[i-1][2]));
}
// 長(zhǎng)度-不能休息的最大值==休息的最小值
return length - Math.max(dp[length][0],Math.max(dp[length][1],dp[length][2]));
}
}
