DP:最小调整次数

描述

给出两个数列，求使第一个数列严格降序，第二个数列严格升序的最少交换次数
若无法交换成严格有序，返回“-1”

示例1
输入：
[5,4,3,2,1],[1,2,3,4,5]
返回值：
0
说明：
排列已经满足要求，不需要交换。

示例2
输入：
[1,2,3,4,5],[5,4,3,2,1]
返回值：
4

示例3
输入：
[3,2,1],[1,3,3]
返回值：
-1
说明：
不能满足要求，返回 -1。

求解思路

问题求解上下两个数组最少交换次数，采取动态规划的思路，即：
dp1[i]=k 表示第i列不需要调整即可满足要求，最少调整次数=k
dp2[i]=k 表示第i列需要调整，最少调整次数=k

显然：dp1[0]=0;dp2[0]=1
那么从1开始，当讨论到第i列时，可能有以下情况满足要求
arr1[i]<arr1[i-1] && arr2[i]>arr2[i-1] 其①
即新来的i列已经符合要求，无需任何调整 =》dp1[i]=dp1[i-1]

代码实现

 int arrange(vector<int>& firstRow, vector<int>& secondRow) {
        // write code here
        
      int len=firstRow.size();//长度
      //dp1[i]=k  表示第i列不作交换 最少的交换次数为k
       //dp2[i]=k 表示第i列作交换   最少的交换次数为k
      vector<int> dp1(len,INT_MAX);
      vector<int> dp2(len,INT_MAX);  
      dp1[0]=0;
      dp2[0]=1;
        
      for(int i=1;i<len;i++)
      {
          //使得  第一行满足递减  第二行满足递增  因此在i列与i-1列中寻找可能
          if(firstRow[i]<firstRow[i-1] && secondRow[i]>secondRow[i-1])   //也就是当前i列的两个数  不作调整即可与 i-1列不作调整构成合理序列
          {
              dp1[i]=dp1[i-1];
          }
          
          if(secondRow[i]<secondRow[i-1] && firstRow[i]>firstRow[i-1]  )  //刚好反了一下
          {
              if(dp2[i-1]!=INT_MAX)
                   dp2[i]=dp2[i-1]+1;  //那么在之前交换的基础之上+加1次交换   第i-1列 第i列均交换
          }
          
          if(firstRow[i]<secondRow[i-1] && secondRow[i]>firstRow[i-1])
          {
              
              dp1[i]=min(dp1[i],dp2[i-1]);    //当前列不调整  之前i-1列调整     注意这儿dp1[i]可能之前被修改
          }
          if(firstRow[i]>secondRow[i-1] && secondRow[i]<firstRow[i-1])
          {
              if(dp1[i-1]!=INT_MAX)
                  dp2[i]=min(dp2[i],dp1[i-1]+1);  //必须在i-1列不调整的情况下  交换当前列
          }      
      }
        
       int res=min(dp1[len-1],dp2[len-1]);
       if(res==INT_MAX)
              return -1;
          else
              return res;

    }