801. 使序列递增的最小交换次数（Medium）

题解

确定状态

首先动态规划一定要分子问题，而且子问题必须是最优解。

首先想到这样做，dp[i] 记录了前 i 位上最少需要翻转几次dp[i - 1] 记录了前 i - 1 位上最少需要翻转几次 只要找到 dp[i] 和 dp[i - 1] 的转移方程即可

但是缺了点东西！！！

为了更好的理解题目，加上一个例子 2 7 6 3 5 9

dp[1] 在翻转的时候，dp[2] 是不知道的，所以一定不够，需要加上标记是否翻转。

所以，最后的状态是

dp[0][i] 记录了当 i 不翻转的时候，前 i 位上最少需要翻转几次 dp[1][i] 记录了当 i 翻转的时候，前 i 位上最少需要翻转几次，

转移方程

当 A[i] > A[i - 1] AND B[i] > B[i - 1] 各自严格递增的情况下

dp[0][i] = dp[0][i - 1],  # 不翻转
# 镜像操作
dp[1][i] = dp[1][i - 1] + 1 # 前一位跟着翻转

A[i] > B[i - 1] AND B[i] > A[i - 1] A、B 交叉严格递增的情况下

dp[0][i] = dp[1][i - 1]  # 不翻转
dp[1][i] = dp[0][i - 1] + 1 #  前一位不动

初始条件 && 边界条件

# 初始条件
dp[0][0] = 0
dp[1][0] = 1

# 边界条件
dp[0][i] = dp[0][i] = Inf , i > 0 

Python 示例

class Solution:
    def minSwap(self, A: List[int], B: List[int]) -> int:
        dp = [[math.inf] * len(A) for _ in range(2)]
        dp[0][0] = 0
        dp[1][0] = 1
        for i in range(1, len(A)):
            if A[i] > A[i - 1] and B[i] > B[i - 1]:
               dp[0][i] = min(dp[0][i], dp[0][i - 1])  # 不翻转
               # 镜像操作
               dp[1][i] = min(dp[1][i], dp[1][i - 1] + 1) # 前一位跟着翻转
            if A[i] > B[i - 1] and B[i] > A[i - 1]:
                dp[0][i] = min(dp[0][i], dp[1][i - 1])  # 不翻转
                dp[1][i] = min(dp[1][i], dp[0][i - 1] + 1) #  前一位不动
        return min(dp[0][len(A) - 1], dp[1][len(A) - 1])