# 70 Climbing Stairs
DP 題目實在太不熟,要多練習。租學者可以先用暴力解法,再找出其中規則
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?
Note: Given n will be a positive integer.
input: 總共 n 階, 你可以一次走一步或兩步
output: 幾種方式可以到
Example 1:
Input: 2
Output: 2
Explanation: There are two ways to climb to the top.
1. 1 step + 1 step
2. 2 steps
Example 2:
Input: 3
Output: 3
Explanation: There are three ways to climb to the top.
1. 1 step + 1 step + 1 step
2. 1 step + 2 steps
3. 2 steps + 1 step
*/
/**
* @param {number} n
* @return {number}
*/
var climbStairs = function(n) {}
怎麼解
一看題目就覺得難果然是 DP , DP 對我來說真的是太不熟練了。這題其實是變相費式數列
n = 1, result 1 (爬一階 1 次)
n = 2, result 1 + 1 (爬一階 2 次 / 爬兩階 1 次)
n = 3, result 1 + 2 (前面兩個相加) (爬一階 3 次 / 爬兩階 1 次 + 爬一階 1 次 / 爬一階 1 次 + 爬兩階 1 次 )
n = 4, result = 3 + 2 (前面兩個相加)
if(n == 1){
return 1
}else if(n == 2){
return 2
}
lookup[i] = lookup[i-1] + lookup[i-2];
是不是很像 XD
var climbStairs = function(n) {
if(n == 1){
return 1
}else if(n == 2){
return 2
}
let lookup = [1,2]; // 1 step 有一種方式, 2 step 有兩種方式
for(let i = 2; i< n ; i++){
lookup[i] = lookup[i - 1] + lookup[i - 2]
}
return lookup[n - 1]
};
console.log(climbStairs(3))
Last updated
Was this helpful?