steps style n-2 递归 climb n-1 turn reac pan
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.
1.递归(超时)
- public int climbStairs(int n) {
- if (n <= 0) return 0;
- if (n == 1) return 1;
- if (n == 2) return 2;
- return climbStairs(n - 1) + climbStairs(n - 2);
- }
2.动态规划
- public int climbStairs(int n) {
- if (n == 0 || n == 1 || n == 2) return n;
- int[] dp = new int[n + 1];
- dp[0] = 0;
- dp[1] = 1;
- dp[2] = 2;
- for (int i = 3; i <= n; i++) {
- dp[i] = dp[i - 1] + dp[i - 2];
- }
- return dp[n];
- }
[leetcode] 70. Climbing Stairs 解题报告
来源: http://www.bubuko.com/infodetail-2327142.html