leetcode -- 70. Climbing Stairs

本文主要是介绍leetcode -- 70. Climbing Stairs，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目描述

题目难度：Easy
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. step + 1 step
2. steps

• Example 2:

Input: 3
Output: 3
Explanation: There are three ways to climb to the top.

1. step + 1 step + 1 step
2. step + 2 steps
3. steps + 1 step

AC代码1

递归，超时了

class Solution {int res = 0;public int climbStairs(int n) {climbStairsCore(0, n);return res;}private void climbStairsCore(int start, int n){if(start > n) return;if(start == n) {res++;return;}climbStairsCore(start + 1, n);climbStairsCore(start + 2, n);}
}

AC代码2

动态规划，时间复杂度过高

class Solution {public int climbStairs(int n) {if(n == 1) return 1;if(n == 2) return 2;int[] res = new int[n];res[0] = 1;res[1] = 2;for(int i = 2;i < n;i++) res[i] += res[i - 1] + res[i - 2]; return res[n - 1];}
}

AC代码3

public class Solution {//动态规划 分析问题 此题类似于斐波那契数public int climbStairs(int n) {// base casesif(n <= 0) return 0;if(n == 1) return 1;if(n == 2) return 2;int one_step_before = 2;int two_steps_before = 1;int all_ways = 0;for(int i=2; i<n; i++){all_ways = one_step_before + two_steps_before;two_steps_before = one_step_before;one_step_before = all_ways;}return all_ways;}
}

这篇关于leetcode -- 70. Climbing Stairs的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---