Climb the stairs

Description: Suppose you are climbing the stairs. It takes n steps to get to the top.

You can climb 1 or 2 steps at a time. How many different ways can you climb to the top of a building?

Note: given n is a positive integer.

See the LeetCode website for an example.

Source: LeetCode Link: https://leetcode-cn.com/probl… Copyright belongs to collar network. Commercial reprint please contact the official authorization, non-commercial reprint please indicate the source.

Problem resolution

A typical Fibonacci sequence, because there are two ways to go to the NTH step, either from the NTH minus one step or from the NTH minus two steps, so the total number of ways to go to the NTH step is equal to the number of ways to go to the NTH minus one step plus the number of ways to go to the n-second step.

Solution 1: Recursion

Recursively calling the same method first returns n if n is 1 or 2; If n is greater than 2 then we call this method recursively
f(n) = f(n - 1) + f(n - 2).

Solution 2: Iterate

First of all, if n is 1 or 2, it just returns n; If n is greater than 2, then record the two previous values as lastOne and lastTwo, then the current value is the sum of these two values, and update the values of lastOne and lastTwo until the iteration reaches n. 

Public class LeetCode_070 {/** * / Submitted beyond the time limit the @ param n * * * @ return * / public static int climbStairs (int n) {if (n = = 1 | | n = = 2) {return n. } return climbStairs(n - 1) + climbStairs(n - 2); } / iteration @ param n * * * * * * @ return * / public static int climbStairs2 (int n) {if (n = = 1 | | n = = 2) {return n. } int lastOne = 1, lastTwo = 2, result = -1; for (int i = 3; i <= n; i++) { result = lastOne + lastTwo; lastOne = lastTwo; lastTwo = result; } return result; } public static void main(String[] args) { System.out.println(climbStairs(45)); System.out.println(climbStairs2(45)); }}

【 Daily Message 】
Your good fortune is stored in your strength as well as your unknown efforts. The harder you work, the luckier you will be.