2022/04/14

Leetcode Note: Go - Climbing Stairs

Climbing Stairs - LeetCode
https://leetcode.com/problems/climbing-stairs/

Go 言語で取り組んだメモ

所感

全くわからん
偶数か奇数か判定して、使用可能な 2 を 1, 1 に置き換えられるパターン数をカウントする？
わからん・・・

実装準備

func climbStairs(n int) int {
    return 0
}

func main() { 
    n := 3
    fmt.Println(climbStairs(3))
}

Solutions

Python/JS/Go/C++ O(n) DP // Fibonacci [w/ Hint ] - LeetCode Discuss
https://leetcode.com/problems/climbing-stairs/discuss/628462/PythonJSGoC%2B%2B-O(n)-DP-Fibonacci-w-Hint

Golang 0ms DP - LeetCode Discuss
https://leetcode.com/problems/climbing-stairs/discuss/25379/Golang-0ms-DP

go solution - LeetCode Discuss
https://leetcode.com/problems/climbing-stairs/discuss/1567398/go-solution

Fibonacci を Dynamic Programming で解くのがメジャーな解法っぽい

回答

Python/JS/Go/C++ O(n) DP // Fibonacci [w/ Hint ] - LeetCode Discuss
https://leetcode.com/problems/climbing-stairs/discuss/628462/PythonJSGoC%2B%2B-O(n)-DP-Fibonacci-w-Hint

func climbStairs(n int) int {

	// key: stair i
	// value: method count of climbing to stair i
	memo := make(map[int]int)

	// initialization on base case
	memo[0] = 1
	memo[1] = 1

	// define inenr function: climb
	var climb func(int) int
	climb = func(i int) int {

		if i <= 1 {
			// base case
			return memo[i]

		} else if val, exist := memo[i]; exist {

			// climb(i) has been computed before, directly look-up memo
			return val

		} else {
			// general cases
			memo[i] = climb(i-1) + climb(i-2)
			return memo[i]
		}

	}

	return climb(n)

}

LeetCode の Discuss 投稿は、別に 1つの投稿に対して 1つの言語解説じゃなくても良いんだな・・・
- むしろ色んな言語での解法も記載すると、 View 数も評価も良いっぽい
解法
- フィボナッチ数と再帰を使う
- Climbing Stairs は Method to level n = Method to level (n-1) + Method to level (n-2) と表現できる
- つまり f( n ) = f( n - 1 ) + f( n - 2 )
- これを Top Down DP で解く
Go での実装
- 数値を保持するための変数として memo を定義
  - memo := make(map[int]int)
  - memo[0] = 1
  - memo[1] = 1
- 再帰関数である climb を実装
  - 引数で受け取った i が 1 以下なら return memo[i]
  - i が 2 以上、かつ、 memo[i] に値があれば return val 実質 return memo[i]
  - それら以外であれば memo[i] = climb(i-1) + climb(i-2) して return memo[i]
    - これが再帰呼び出しになる
- climb に n を指定して呼び出す

climb が呼び出された際に i を出力するよう修正した実行例

n = 1, return 1
climb i:  1

n = 2, return 2
climb i:  2
climb i:  1
climb i:  0

n = 3, return 3
climb i:  3
climb i:  2
climb i:  1
climb i:  0
climb i:  1

n = 4, return 5
climb i:  4
climb i:  3
climb i:  2
climb i:  1
climb i:  0
climb i:  1
climb i:  2

n = 5, return 8
climb i:  5
climb i:  4
climb i:  3
climb i:  2
climb i:  1
climb i:  0
climb i:  1
climb i:  2
climb i:  3

解説を見たものの腹落ちした感じはせず・・・
DP をもっと理解する必要がありそう