Pythonの連続する3つの要素から少なくとも1つの要素を取得することにより、最小の合計サブシーケンスを見つけるプログラム

numsと呼ばれる数のリストがあるとすると、3つの連続する数のすべてのグループに対して少なくとも1つの数が選択されるように、与えられたリストから最小の合計サブシーケンスを見つける必要があります。指定されたリストの長さが3未満の場合でも、番号を選択する必要があります。

したがって、入力がnums =[2、3、4、5、6、7]の場合、2と5を選択できるため、出力は7になります。

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

• n：=numsのサイズ
• nが0と同じ場合、
  • 0を返す
• nが1と同じ場合、
  • return nums [0]
• nが2と同じ場合、
  • 最小のnums[0]とnums[1]を返します
• table：=サイズnのリストと0で埋める
• table [0]：=nums [0]
• table [1]：=nums [1]
• table [2]：=nums [2]
• 3からnの範囲のiについては、
  • table [i]：=nums [i] + table [i-3]、table [i-2]、table[i-1]の最小値
• res：=テーブル[n-1]、テーブル[n-2]、テーブル[n-3]の最小値
• return res

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

サンプルコード

class Solution:
   def solve(self, nums):
      n = len(nums)
      if n == 0:
         return 0
      if n == 1:
         return nums[0]
      if n == 2:
         return min(nums[0], nums[1])
      table = [0] * n

      table[0] = nums[0]
      table[1] = nums[1]
      table[2] = nums[2]

      for i in range(3, n):
         table[i] = nums[i] + min(table[i - 3], table[i - 2], table[i - 1])

         res = min(table[n - 1], table[n - 2], table[n - 3])
      return res

ob = Solution()
nums = [2, 3, 4, 5, 6, 7]
print(ob.solve(nums))

入力

[2, 3, 4, 5, 6, 7]

出力

7