[leetcode] 801. Minimum Swaps To Make Sequences Increasing

[leetcode] 801. Minimum Swaps To Make Sequences Increasing

Description

We have two integer sequences A and B of the same non-zero length.

We are allowed to swap elements A[i] and B[i]. Note that both elements are in the same index position in their respective sequences.

At the end of some number of swaps, A and B are both strictly increasing. (A sequence is strictly increasing if and only if A[0] < A[1] < A[2] < … < A[A.length - 1].)

Given A and B, return the minimum number of swaps to make both sequences strictly increasing. It is guaranteed that the given input always makes it possible.

Example:

Input: A = [1,3,5,4], B = [1,2,3,7]Output: 1Explanation: Swap A[3] and B[3]. Then the sequences are:A = [1, 3, 5, 7] and B = [1, 2, 3, 4]which are both strictly increasing.

Note:

A, B are arrays with the same length, and that length will be in the range [1, 1000].A[i], B[i] are integer values in the range [0, 2000].

分析

题目的意思是：求使两个序列递增的最小交换次数。

用二维DP来计算：

dp[i][0]表示不交换i，使得[0, i]严格递增的最小swap数dp[i][1]表示交换i，使得[0, i]严格递增的最小swap数再看状态转移方程，在每一步判断，我们要不要交换，A[i-1]

代码

class Solution {public: int minSwap(vector& A, vector& B) { int n=A.size(); vector> dp(n,vector(2,INT_MAX)); dp[0][0]=0; dp[0][1]=1; for(int i=1;i

参考文献

​​801. Minimum Swaps To Make Sequences Increasing​​

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。