Climbing Stairs (E)
題目
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.
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
題意
給定一個高度為n的樓梯，每次可以向上走1層或2層，統計可以登頂的方法的個數，
思路
動態規劃：dp[i]代表能夠走到第i層的方法的個數，而第i層只可能由第i-1層走1層到達，或由第i-2層走2層到達，所以有 \(dp[i]=dp[i-1]+dp[i-2]\)，
遞回：從當前層i走到最高層的方法數等于從i+1層走到最高層的方法數加上i+2層走到最高層的方法數，
代碼實作
Java
動態規劃
class Solution {
public int climbStairs(int n) {
int[] dp = new int[n];
dp[0] = 1;
for (int i = 1; i < n; i++) {
dp[i] = dp[i - 1] + (i > 1 ? dp[i - 2] : 1);
}
return dp[n - 1];
}
}
遞回
class Solution {
public int climbStairs(int n) {
int[] ways = new int[n + 1]; // 避免重復運算
return findWays(0, n, ways);
}
// 回傳從第i層走到第n層的方法數
private int findWays(int i, int n, int[] ways) {
if (i == n) {
return 1;
}
if (i > n) {
return 0;
}
if (ways[i] > 0) {
return ways[i];
}
ways[i] = findWays(i + 1, n, ways) + findWays(i + 2, n, ways);
return ways[i];
}
}
JavaScript
/**
* @param {number} n
* @return {number}
*/
var climbStairs = function (n) {
let dp = [1, 2]
for (let i = 2; i < n; i++) {
dp[i] = dp[i - 2] + dp[i - 1]
}
return dp[n - 1]
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/10659.html
標籤：其他