# 0801. Minimum Swaps To Make Sequences Increasing
###### tags: `Leetcode` `Hard` `Dynamic Programming`
Link: https://leetcode.com/problems/minimum-swaps-to-make-sequences-increasing/
## 思路
对于第i轮的决策而言，是否交换A[i]和B[i]，完全取决于A[i-1]和B[i-1]是否交换
显然这是第I类基本型的DP：第i轮的状态只与第i-1轮的状态有关，且每轮的“状态”只有两种：交换或者不交换

如果当前不交换 上一轮也不能交换，如果当前交换了 上一轮也要交换

如果当前不交换 上一轮需要交换，如果当前交换了 上一轮不需要交换

**求min的题每一轮先要设一个极值** 这里设unchanged和changed都为nums1.length 这样求Math.min的时候才不会直接变成上一轮的值(因为这一轮的值通常会大于等于这一轮)
## Code

class Solution {
    public int minSwap(int[] nums1, int[] nums2) {
        int unchanged = 0, changed = 1;
        for(int i=1; i<nums1.length; i++){
            int unchanged2 = nums1.length, changed2 = nums1.length;
            if(nums1[i-1]<nums1[i] && nums2[i-1]<nums2[i]){
                unchanged2 = unchanged;
                changed2 = changed+1;
            }
            if(nums1[i-1]<nums2[i] && nums2[i-1]<nums1[i]){
                unchanged2 = Math.min(unchanged2, changed);
                changed2 = Math.min(changed2, unchanged+1);
            }
            unchanged = unchanged2;
            changed = changed2;
        }
        return Math.min(unchanged, changed);
    }
}