Pythonでリストを増加しないリストに変換するために必要な操作の数を見つけるためのプログラム

numsという番号のリストがあるとします。ここで、2つの連続する値を取得し、それらの合計を取得して1つの値にマージする操作について考えてみましょう。リストが増加しないようにするために必要な操作の最小数を見つける必要があります。

したがって、入力がnums =[2、6、4、10、2]のような場合、[2、6]をマージして[8、4、10、2]を取得し、次に[8、4、10、2]を取得できるため、出力は2になります。 [8、4]をマージして[12、10、2]を取得します。

これを解決するには、次の手順に従います-

• numsが空の場合、

  • 0を返す

• numsの最後に-infを挿入します

• N：=numsのサイズ

• dp：=サイズNのリストで、0で埋めます

• arr：=サイズNのリストで、0で埋めます

• p：=arrのサイズ

• arr [p-1]：=nums [N-1]

• arr [p−2]：=nums [N−2]

• N − 3から0の範囲のiの場合、1ずつ減少します。

  • j：=i

  • x：=nums [j]

  • j

    • j：=j + 1

    • x：=x + nums [j]

  • dp [i]：=j − i + dp [j + 1]

  • arr [i]：=x

• dp [0]

  を返します

理解を深めるために、次の実装を見てみましょう-

例

class Solution:
   def solve(self, nums):
      if not nums:
         return 0
      nums.append(float("−inf"))
      N = len(nums)
      dp = [0] * N
      arr = [0] * N
      arr[−1] = nums[−1]
      arr[−2] = nums[−2]
      for i in range(N − 3, −1, −1):
         j = i
         x = nums[j]
         while j < N − 1 and x < arr[j + 1]:
            j += 1
            x += nums[j]
         dp[i] = j − i + dp[j + 1]
         arr[i] = x
      return dp[0]
ob = Solution()
nums = [2, 6, 4, 10, 2]
print(ob.solve(nums))

入力

[2, 6, 4, 10, 2]

出力

2