Leetcode Note: Go - Min Cost Climbing Stairs
Min Cost Climbing Stairs - LeetCode
https://leetcode.com/problems/min-cost-climbing-stairs/
- Go 言語で取り組んだメモ
所感
- int 配列 nums が渡される
- cost[i] が階段の i 番目のステップコスト
- コストを払ったら 1 or 2 段登れる
- index 0 のステップから開始することも index 1 のステップから開始することもできる
- フロアの最上部に到達するための最小コストを return する
回答
Golang 8ms using DP - LeetCode Discuss
https://leetcode.com/problems/min-cost-climbing-stairs/discuss/617497/Golang-8ms-using-DP
func minCostClimbingStairs(costs []int) int {
memo := map[int]int{}
return min(
helper(costs, 0, memo),
helper(costs, 1, memo),
)
}
func min(a, b int) int {
if a < b {
return a
}
return b
}
func helper(costs []int, pos int, memo map[int]int) int {
if cost, ok := memo[pos]; ok {
return cost
} else if pos >= len(costs) {
return 0
}
cost := costs[pos]
memo[pos] = cost + min(
helper(costs, pos+1, memo),
helper(costs, pos+2, memo))
return memo[pos]
}