You are climbing a staircase. 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
Constraints:
1 <= n <= 45
爬楼梯。
假设你正在爬楼梯。需要 n 阶你才能到达楼顶。
每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢?
注意:给定 n 是一个正整数。
来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/climbing-stairs
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。
这道题有两种解法,一种是数学解法,一种是动态规划。
首先是数学解法,这个题本质上是斐波那契数列。当输入为1, 2, 3, 4, 5, 6, 7, 8, 9, 10时,观察输出为1, 2, 3, 5, 8, 13, 21, 34, 55, 89。所以做法就很直观了。
迭代
时间O(n)
空间O(n)
JavaScript实现
1 /** 2 * @param {number} n 3 * @return {number} 4 */ 5 var climbStairs = function (n) { 6 const climing = []; 7 // using variables because they allocate a memory only once 8 let minusTwoSteps = 1; 9 if (n === 1) { 10 return 1; 11 } 12 let minusOneStep = 2; 13 if (n === 2) { 14 return 2; 15 } 16 let current = 0; 17 for (let i = 3; i <= n; i++) { 18 current = minusTwoSteps + minusOneStep; // current step - is a sum of two previous ones 19 minusTwoSteps = minusOneStep; // -2 steps for next iteration would be current - first 20 minusOneStep = current; // -1 step for next iteration would be our current 21 } 22 return current; 23 };
Java实现
1 class Solution { 2 public int climbStairs(int n) { 3 int first = 1; 4 int second = 2; 5 if (n <= 2) { 6 return n; 7 } 8 int cur = 0; 9 for (int i = 3; i <= n; i++) { 10 cur = first + second; 11 first = second; 12 second = cur; 13 } 14 return cur; 15 } 16 }
DP
dp[i] 数组的定义是跑到第 i 层楼的时候,上楼梯的组合数是多少。几个初始值是 dp[0] = 0, dp[1] = 1, dp[2] = 2。因为每次既可以爬一层楼,也可以爬两层楼,所以当你需要知道第i层楼的爬法的时候,你需要看的是我爬到 i - 2 层楼有几种爬法和我爬到 i - 1 层楼有几种爬法。所以状态转移方程就是 dp[i] = dp[i - 1] + dp[i - 2]。
时间O(n)
空间O(n)
JavaScript实现
1 /** 2 * @param {number} n 3 * @return {number} 4 */ 5 var climbStairs = function (n) { 6 if (n === 0) return 0; 7 let dp = [n + 1]; 8 dp[0] = 1; 9 dp[1] = 1; 10 for (let i = 2; i <= n; i++) { 11 dp[i] = dp[i - 1] + dp[i - 2]; 12 } 13 return dp[n]; 14 };
Java实现
1 class Solution { 2 public int climbStairs(int n) { 3 if (n == 0) return 0; 4 int[] dp = new int[n + 1]; 5 dp[0] = 1; 6 dp[1] = 1; 7 for (int i = 2; i <= n; i++) { 8 dp[i] = dp[i - 1] + dp[i - 2]; 9 } 10 return dp[n]; 11 } 12 }
相关题目