上上下下

题目

牛牛是一位优秀的程序员。最近，牛牛在的公司要办年会了。
牛牛所在的组要表演一个比较有意思的大合唱，程序员们站在第一排，产品经理们站在第二排。为了让年会节目更有吸引力，牛牛在设计站位上下了功夫：从左往右，程序员们由高到矮进行站位，而产品经理们则按由矮到高进行站位，两个队列的上下场方向也不一样，这样从上场、演唱到下场，整个队列看起来就像一个波浪开合，非常有趣。
牛牛他们排练完就回去工作了，转眼就来到了年会当天。当大家换上了表演用的服装后，牛牛傻了眼：之前排练的时候大家穿的都是自己的鞋，这下统一更换成演出用的鞋之后，原来两个排好的队列不再按身高有序了！然而，表演马上就要开始了，由于站位和演出效果有关，大家的站位又不能进行调整，这可怎么办？
聪明的牛牛想到了一个补救办法：如果能让相对站在同一列的产品经理和程序员互换位置，最后也能满足从左往右第一排从高到矮，第二排从矮到高，那也能满足演出效果。然而，就在这个关头，牛牛被叫去核对音乐和灯光了，他只好把这个任务交给你。他会把现在第一排和第二排的身高数据给你，请你告诉他最少需要交换几对演出成员才能满足之前的要求。如果怎么交换都不能满足，请你返回 -1。

代码

import java.util.*;


public class Solution {
    /**
     * 计算最小交换次数
     * @param firstRow int整型一维数组 第一行的身高数据
     * @param secondRow int整型一维数组 第二行的身高数据
     * @return int整型
     */
    public int arrange (int[] firstRow, int[] secondRow) {
        // write code here
        int n=firstRow.length;
        int[][] dp=new int[2][n];
        Arrays.fill(dp[0],Integer.MAX_VALUE);
        Arrays.fill(dp[1],Integer.MAX_VALUE);
        // 类似股票问题，dp[0][i]第i列没交换的最小次数,dp[1][i]第i列有交换的最小次数
        dp[0][0]=0;
        dp[1][0]=1;
        for(int i=1;i<n;i++){
            if(firstRow[i]<firstRow[i-1]&&secondRow[i]>secondRow[i-1]){
                dp[0][i]=Math.min(dp[0][i],dp[0][i-1]);
            }
            if(firstRow[i]>firstRow[i-1]&&secondRow[i]<secondRow[i-1]){
                if(dp[1][i-1]!=Integer.MAX_VALUE)
                    dp[1][i]=Math.min(dp[1][i],dp[1][i-1]+1);
            }
            if(firstRow[i]<secondRow[i-1]&&secondRow[i]>firstRow[i-1]){
                dp[0][i]=Math.min(dp[1][i-1],dp[0][i]);
            }
            if(firstRow[i]>secondRow[i-1]&&secondRow[i]<firstRow[i-1]){
                if(dp[0][i-1]!=Integer.MAX_VALUE)
                    dp[1][i]=Math.min(dp[0][i-1]+1,dp[1][i]);
            }
        }
        int res=Math.min(dp[0][n-1],dp[1][n-1]);
        if(res==Integer.MAX_VALUE) return -1;
        return res;
    }
}

引用自 @Joseph1314