(DP)801. 시퀀스를 증가시키는 최소 교환 횟수

우리는 길이가 같고 비어 있지 않은 두 개의 정형 수조 A와 B가 있다.
우리는 A[i]와 B[i]의 원소를 교환할 수 있다.이 두 원소는 각자의 서열에서 같은 위치에 있어야 한다는 것을 주의해라.
일부 요소를 교환한 후에 수조 A와 B는 모두 엄격하게 증가해야 한다(수조가 엄격하게 증가하는 조건은 A[0] < A[1] < A[2] <...< A[A.length - 1]).
배열 A와 B를 지정하면 두 배열 모두 엄격한 증가 상태를 유지하도록 하는 최소 스왑 횟수를 반환합니다.주어진 입력이 항상 유효하다고 가정하십시오.
예: 입력: A=[1,3,5,4], B=[1,2,3,7] 출력: 1 해석: A[3]와 B[3]를 교환한 후 두 개의 그룹은 다음과 같다. A=[1,3,5,7], B=[1,2,3,4] 두 그룹은 모두 엄격하게 증가했다.참고:
A, B 두 배열의 길이는 항상 같고 길이의 범위는 [1, 1000]입니다.A[i], B[i]는 모두 [0,2000] 구간 내의 정수이다.
출처: 리코더 링크:https://leetcode-cn.com/problems/minimum-swaps-to-make-sequences-increasing저작권은 인터넷 소유에 귀속된다.상업 전재는 관공서에 연락하여 권한을 수여하고 비상업 전재는 출처를 밝혀 주십시오.
문제풀이: 오랫동안 dp를 쓰지 않았는데도wa는 여러 발을 썼다. dp[i][0]: 대표 i위는 뒤집지 않는다.
dp[i][1]: i를 대표하여 뒤집기;
1. A[i-1]>=A[i]||B[i-1]>=B[i]일 때 뒤집기:
뒤집기 상황: (1) i-1위를 뒤집으면 dp[i][0]=dp[i-1]이 있다[1]
(2) i-1위를 뒤집으면 dp[i][1]=dp[i-1][0]+1이 있다.
2. B[i-1]>=A[i]||A[i-1]>=B[i]일 경우 (뒤집기 불가) 또는 (i위와 i-1위 모두 동시에 뒤집기):
상태 전환: dp[i][0]=dp[i-1][0]//뒤집지 않음dp[i][1]=dp[i-1][1]+1//모두 뒤집기
3. 나머지 상황은 (A[i]>=A[i-1]과 A[i]>=B[i-1]) & (B[i]>=B[i-1] 및 B[i]>=A[i-1])이다. 이렇게 하면 뒤집거나 안 뒤집을 수 있다.
상태 전환: dp[i][0]=min(dp[i-1][0], dp[i-1][1])//뒤집지 않음 dp[i][1]=min(dp[i-1][0], dp[i-1][1])+1//뒤집기

class Solution {
public:
    int dp[1005][2];
    int minSwap(vector& a, vector& b) {
       
        int len=a.size();
        dp[0][1]=1;
        for(int i=1;i=a[i]||b[i-1]>=b[i]){
                dp[i][1]=dp[i-1][0]+1;
                dp[i][0]=dp[i-1][1];
            }  
            else if(b[i-1]>=a[i]||a[i-1]>=b[i]){
                dp[i][0]=dp[i-1][0];
                dp[i][1]=dp[i-1][1]+1;
            }
            else{
                dp[i][0]=min(dp[i-1][0],dp[i-1][1]);
                dp[i][1]=min(dp[i-1][0],dp[i-1][1])+1;
            }
        }
        return min(dp[len-1][0],dp[len-1][1]);
    }
};