Pythonで解く「最小コストの階段登り」問題：動的計画法による実装方法

各段に負でないコスト値 cost[i] が割り当てられた階段があるとします。コストを支払うことで、1段または2段を一度に登ることができます。ここでの目的は、階段の最上部に到達するための最小コストを求めることです。なお、スタート地点はインデックス0の段、またはインデックス1の段のどちらかを自由に選ぶことができます。

例として、入力が cost = [12,17,20] の場合を考えてみましょう。このときの出力は 17 となります。理由は、インデックス1の段からスタートしてコスト17を支払い、そこから直接頂上へ向かうのが最も安く済むためです。

解き方のアプローチ

この問題は動的計画法（DP）を使うことで効率的に解くことができます。手順は以下の通りです。

• cost と同じサイズの配列 dp を作成し、すべて 0 で初期化します
• dp[0] := cost[0]
• cost のサイズが2以上の場合は、dp[1] := cost[1]
• i が 2 から cost のサイズ - 1 までの範囲で、次の処理を繰り返します
  • dp[i] := cost[i] + min(dp[i-1], dp[i-2])
• 最後に min(dp[-1], dp[-2]) を返します

各 dp[i] には「i 番目の段に立つまでに必要な最小コスト」が格納されます。現在の段のコストに、1段前と2段前のうち小さい方のコストを加えることで、最適な経路が自然と求まる仕組みです。

実装例

それでは、実際のPythonコードを見て理解を深めましょう。

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

このアルゴリズムの計算量は時間・空間ともに O(n) です。階段の段数が増えても線形時間で処理できるため、LeetCodeなどで頻出する定番の動的計画法の練習問題としておすすめです。さらに工夫すれば、直前の2つの値だけを保持する方法で空間計算量を O(1) まで削減することも可能です。