未分類

Climbing Stairs

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
}

總結:

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

分享到