2022/09/12

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]
}

See Also