Pythonでの最小コスト登山階段

階段があると仮定します。ここで、i番目のステップには負でないコスト値cost[i]が割り当てられます。費用を支払うとき、私たちは1つまたは2つのステップを登ることができます。フロアの最上部に到達するための最小コストを見つける必要があります。また、インデックス0のステップから開始することも、インデックス1のステップから開始することもできます。

したがって、入力がcost =[12,17,20]の場合、出力は17になります。そのコストを支払ってトップに移動する必要があるため、ステップ1から開始するのに最も安いポジションです。

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

• dp：=コストと同じサイズの配列で、0で埋めます
• dp [0]：=コスト[0]
• コストのサイズ>=2の場合、
  • dp [1]：=コスト[1]
• コストのサイズが2から1の範囲のiの場合、実行します
  • dp [i]：=コスト[i]+最小のdp[i-1]、dp [i-2]
• dp [-1]、dp[-2]の最小値を返す

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

例

class Solution:
   def minCostClimbingStairs(self, cost):
      dp = [0] * len(cost)
      dp[0] = cost[0]
      if len(cost) >= 2:
         dp[1] = cost[1]
      for i in range(2, len(cost)):
         dp[i] = cost[i] + min(dp[i-1], dp[i-2])
      return min(dp[-1], dp[-2])
ob = Solution()
print(ob.minCostClimbingStairs([12,17,20]))

入力

[12,17,20]

出力

17