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을 반환
• 그렇지 않으면 i가 0과 같을 때
  • dp(i + 1, False) 및 1 + dp(i + 1, True)의 최소값을 반환
• 그렇지 않으면
  • 이전_A :=A[i - 1]
  • 이전_B :=B[i - 1]
  • prev_swapped가 True이면
    • prev_A 및 prev_B 교체
  • A[i] <=prev_A 또는 B[i] <=prev_B이면
    • 1 + dp(i + 1, True)를 반환
  • 그렇지 않으면
    • ans :=dp(i + 1, False)
    • A[i]> prev_B 및 B[i]> prev_A이면
      • ans :=ans의 최소값, 1 + dp(i + 1, True)
    • 반환
  • 메인 메소드에서 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