リストを厳密に作成するために必要な操作の最小数を見つけるためのプログラムPythonで増加

AとBという2つの番号のリストがあり、それらが同じ長さであるとします。ここで、番号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）を返します
• それ以外の場合、
  • prev_A：=A [i-1]
  • prev_B：=B [i-1]
  • prev_swappedがTrueの場合、
    • prev_Aとprev_Bを入れ替える
  • A [i]<=prev_AまたはB[i]<=prev_Bの場合、
    • return 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