本题的链接是：假期

题目描述

由于业绩优秀，公司给小Q放了 n 天的假，身为工作狂的小Q打算在在假期中工作、锻炼或者休息。他有个奇怪的习惯：不会连续两天工作或锻炼。只有当公司营业时，小Q才能去工作，只有当健身房营业时，小Q才能去健身，小Q一天只能干一件事。给出假期中公司，健身房的营业情况，求小Q最少需要休息几天。

输入描述:

一个整数，表示小Q休息的最少天数

输入例子1:

4
1 1 0 0
0 1 1 0

输出例子1:

2

例子说明1:

当小Q处于位置3时，他可以向前看到位置2,1处的楼，向后看到位置4,6处的楼，加上第3栋小Q可以在第一天工作，第二天或第三天健身，小Q最少休息2天

解题思路-维特比算法

从题目可以知道，小Q的状态只有工作，健身，休息三种状态，我们可以用dp[i][0]、dp[i][1]、dp[i][2]分别表示小Q第i天在工作，健身，休息的时候，他在1~i天有最多有多少天不休息。三种状态可以用到维特比算法以相互转换：
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]));
        }
//        长度-不能休息的最大值==休息的最小值
        return length - Math.max(dp[length][0],Math.max(dp[length][1],dp[length][2]));
    }
}