LeetCode Solutions
70. Climbing Stairs
Time: $O(n)$ Space: $O(n)$
class Solution {
public:
int climbStairs(int n) {
// dp[i] := # of distinct ways to climb to i-th stair
vector<int> dp(n + 1);
dp[0] = 1;
dp[1] = 1;
for (int i = 2; i <= n; ++i)
dp[i] = dp[i - 1] + dp[i - 2];
return dp[n];
}
};
class Solution {
public int climbStairs(int n) {
// dp[i] := # of distinct ways to climb to i-th stair
int[] dp = new int[n + 1];
dp[0] = 1;
dp[1] = 1;
for (int i = 2; i <= n; ++i)
dp[i] = dp[i - 1] + dp[i - 2];
return dp[n];
}
}
class Solution:
def climbStairs(self, n: int) -> int:
# dp[i] := # Of distinct ways to climb to i-th stair
dp = [1, 1] + [0] * (n - 1)
for i in range(2, n + 1):
dp[i] = dp[i - 1] + dp[i - 2]
return dp[n]