Pythonですべてのタスクを完了するための最小時間を見つけるためのプログラム

numsと呼ばれる数値のリストがあり、各値がタスクの完了にかかる時間の単位を決定しているとします。連続していないタスクはスキップできます。すべてのタスクを完了するのにかかる最小時間を見つける必要があります。

したがって、入力がnums =[11、6、8、16]の場合、最初と最後のタスクをスキップできるため、出力は14になります。

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

• n：=numsのサイズ
• table：=n x 2行列を作成し、これを0で埋めます
• table [0、0]：=0
• table [0、1]：=nums [0]
• 1からn-1の範囲のiの場合、do
  • table [i、0]：=table [i-1、1]
  • table [i、1] =（table [i-1、0]およびtable [i-1] [1]の最小値）+ nums [i]
• テーブル行の最小値を返す[n-1]

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

例

class Solution:
   def solve(self, nums):
      n = len(nums)
      table = [[0] * 2 for _ in range(n)]

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

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

      return min(table[n - 1])

ob = Solution()
nums = [11, 6, 8, 16]
print(ob.solve(nums))

入力

[11, 6, 8, 16]

出力

14