未分類

Climbing Stairs

DynamicProgramming, Go, LeetCode

Climbing Stairs

You are climbing a stair case. It takes n steps to reach to the top.

Each time you can either climb 1 or 2 steps. In how many distinct ways can you climb to the top?

提示 解題應用
DynamicProgramming 規律觀察

Default:

1
2
3
func climbStairs(n int) int {
}

解答思路:

也許是解題的敏感度不足，看到此題便很快速的想要用排序組合的方式來運算，好比說4個階梯有2個1步與2個2步的不同走法數就是4!/(2!2!)，在排序組合就是總數!(階)去除上兩個彼此相異數!的乘積，如此一來其它狀況也藉由此方式來算最後總合起來就是結果，聽起來合情合理，可是電腦要算的話光是35階這個數或更小就足以讓你溢位了，所以看來不是以這種方式來解決問題，而最後從整體數序來觀察規律就可以很輕易的將此題給搞定了，1, 2, 3, 5, 8…，其實就是很標準的費式數列: *第三項值 = 第一項值 + 第二項值

程式碼解說:

因為相當單純，就直接用迴圈來做就不使用遞回的方式了，因為費式數列至少需要開頭兩項的值，1階當然只有一種走法，而2階則兩種走法，其餘的階梯算法就只要先把總階數減2(第1,第二階)再不斷用迴圈計算第三項，並暫存前兩項的值即可

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
func climbStairs(n int) int {
	var result int
	tmp1 := 1
	tmp2 := 2
	if n == 1 {
		return 1
	} else if n == 2 {
		return 2
	} else {
		for i := 1; i <= n-2; i++ {
			result = tmp1 + tmp2
			tmp1 = tmp2
			tmp2 = result
		}
	}
	return result
}

完整程式碼:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
func climbStairs(n int) int {
	var result int
	tmp1 := 1
	tmp2 := 2
	if n == 1 {
		return 1
	} else if n == 2 {
		return 2
	} else {
		for i := 1; i <= n-2; i++ {
			result = tmp1 + tmp2
			tmp1 = tmp2
			tmp2 = result
		}
	}
	return result
}

總結:

算階梯走法不是考數學，所以不需要會排序組合，要的只是對數列做觀查，從而發現其為費式數列。

分享到