LeetCode 746. Min Cost Climbing Stairs
はじめに
LeetCode 「746. Min Cost Climbing Stairs」の問題をGoで解きました。
問題
問題文
You are given an integer array cost where cost[i] is the cost of ith step on a staircase. Once you pay the cost, you can either climb one or two steps.
You can either start from the step with index 0, or the step with index 1.
Return the minimum cost to reach the top of the floor.
和訳
整数配列 cost が与えられます。cost[i]は階段の1段目にかかる費用である。costを支払うと、1段か2段のどちらかを登ることができる。
インデックス 0 の段から始めることも、インデックス 1 の段から始めることもできる。
最上階に到達するための最小コストを返す。
例
Input: cost = [10,15,20]
Output: 15
Explanation: You will start at index 1.
- Pay 15 and climb two steps to reach the top.
The total cost is 15.
Input: cost = [1,100,1,1,1,100,1,1,100,1]
Output: 6
Explanation: You will start at index 0.
- Pay 1 and climb two steps to reach index 2.
- Pay 1 and climb two steps to reach index 4.
- Pay 1 and climb two steps to reach index 6.
- Pay 1 and climb one step to reach index 7.
- Pay 1 and climb two steps to reach index 9.
- Pay 1 and climb one step to reach the top.
The total cost is 6.
制約
- 2 <= cost.length <= 1000
- 0 <= cost[i] <= 999
解答1 (動的計画法 Bottom-up)
1段または2段ずつ登れるというルールのもとで、最小コストで最上段に到達する方法を求める問題です。
最上段はcostに含まれていません。
最上段に行くには、cost.length-1 または cost.length-2 の段から登るしかないです。
よって、cost.length-1 までの最小値 と cost.length-2 までの最小値 を比較し、低い方が解となります。
動的計画法(DP) の Bottom-up のアプローチだと解きやすいです。
コード
func minCostClimbingStairs(cost []int) int {
n := len(cost)
dp := make([]int, n)
// 初期値：dp[0],dp[1] はそれぞれの段に直接登るコスト
dp[0] = cost[0]
dp[1] = cost[1]
// i段目にたどり着くための最小コストを順に計算
for i := 2; i < len(cost); i++ {
dp[i] = min(dp[i-1], dp[i-2]) + cost[i]
}
// 最上段はその1つ前 or 2つ前から登る
return min(dp[n-1], dp[n-2])
}
func min(a,b int) int {
if a < b {
return a
}
return b
}
計算量
- 時間的計算量：O(n)
- 各ステップを1回ずつ処理
- 空間的計算量：O(n)
- 配列dpを使って全ステップのコストを保持
解答2(最適化)
解答1について、最適化することが可能です。
直近2つの値だけ保持すればよいので、以下のように書くことができます。
コード
func minCostClimbingStairs(cost []int) int {
prev2 := cost[0]
prev1 := cost[1]
for i := 2; i < len(cost); i++ {
curr := min(prev1, prev2) + cost[i]
prev2 = prev1
prev1 = curr
}
return min(prev1, prev2)
}
func min(a,b int) int {
if a < b {
return a
}
return b
}
計算量
- 時間的計算量：O(n)
- 各ステップを1回ずつ処理
- 空間的計算量：O(1)
- 直前の2つの値を保持すればよい
参考
動的計画法を用いる問題は以下の記事でも解説していますので、参考にしてください。
Discussion