程序以查找严格制作列表所需的最少操作数python中增加

假设我们有两个数字列表，称为A和B，它们的长度相同。现在考虑我们可以执行一个可以交换数字A [i]和B [i]的操作。我们必须找到使两个列表严格增加所需的操作数。

因此，如果输入像A = [2，8，7，10] B = [2，4，9，10]，那么输出将为1，因为我们可以在A中交换7而在B中交换9。列表将类似于A = [2，8，9，10]和B = [2，4，7，10]，它们都是严格增加的列表。

为了解决这个问题，我们将遵循以下步骤：

• 定义一个功能dp()。这需要我，prev_swapped

• 如果A的大小与i相同，则

• 返回0

• 否则当我等于0时

• 返回dp（i + 1，False）和1 + dp（i + 1，True）的最小值

• 除此以外，

• ans：= dp（i + 1，False）

• 如果A [i]> prev_B和B [i]> prev_A，则

• 返回ans

• ans：= ans的最小值，1 + dp（i + 1，True）

• 返回1 + dp（i + 1，真）

• 交换prev_A和prev_B

• prev_A：= A [i-1]

• prev_B：= B [i-1]

• 如果prev_swapped为True，则

• 如果A [i] <= prev_A或B [i] <= prev_B，则

• 除此以外，

• 从主方法调用函数dp(0,False)并返回其值作为结果

让我们看下面的实现以更好地理解：

范例程式码

class Solution:
   def solve(self, A, B):
      def dp(i=0, prev_swapped=False):
         if len(A) == i:
            return 0
         elif i == 0:
            return min(dp(i + 1), 1 + dp(i + 1, True))
         else:
            prev_A = A[i - 1]
            prev_B = B[i - 1]
            if prev_swapped:
               prev_A, prev_B = prev_B, prev_A
            if A[i] <= prev_A or B[i] <= prev_B:
               return 1 + dp(i + 1, True)
            else:
               ans = dp(i + 1)
            if A[i] > prev_B and B[i] > prev_A:
               ans = min(ans, 1 + dp(i + 1, True))
            return ans

         return dp()ob = Solution()A = [2, 8, 7, 10]
B = [2, 4, 9, 10]
print(ob.solve(A, B))

输入值

[2, 8, 7, 10], [2, 4, 9, 10]

输出结果

1