Question
Formatted question description: https://leetcode.ca/all/70.html
70 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?
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
@tag-dp
Algorithm
You can only climb 1 or 2 steps at a time, so the method to climb to the nth layer is either from the n-1 layer one step up, or from the n-2 layer 2 steps up, so the recursive formula is very easy We get: dp[n] = dp[n-1] + dp[n-2].
Code
Java
public class Climbing_Stairs {
public class Solution {
public int climbStairs(int n) {
if (n <= 0) {
return 0;
}
// dp[i], ways to i
int[] dp = new int[n + 1];
dp[0] = 1; // to make dp[2] correct when adding up
dp[1] = 1;
for (int i = 2; i <= n; i++) {
dp[i] = dp[i - 1] + dp[i - 2];
}
return dp[n];
}
}
/*
Time complexity : O(2^n)
Size of recursion tree will be 2^n
*/
class Solution_recursive_cache {
public int climbStairs(int n) {
if (n <= 0) {
return 0;
}
int[] cache = new int[n + 1];
return dfs(n, 0, cache);
}
private int dfs(int n, int current, int[] cache) {
if (current > n) {
return 0;
}
if (current == n) {
return 1;
}
if (cache[current] > 0) {
return cache[current];
}
int combinations = dfs(n, current + 1, cache) + dfs(n, current + 2, cache);
cache[current] = combinations;
return combinations;
}
}
/*
Time complexity : O(2^n)
Size of recursion tree will be 2^n
ref: https://leetcode.com/problems/climbing-stairs/solution/
*/
class Solution_recursive {
public int climbStairs(int n) {
if (n <= 0) {
return 0;
}
return dfs(n, 0);
}
private int dfs(int n, int current) {
if (current > n) {
return 0;
}
if (current == n) {
return 1;
}
return dfs(n, current + 1) + dfs(n, current + 2);
}
}
}