A detailed explanation of stair climbing algorithm based on Go and PHP language

Stair climbing (ES1en-ES2en)

Dry:

Let's say you're climbing the stairs. You need the n level to get to the roof. You can climb one or two steps at a time. How many different ways can you climb to the top of a building? Note: Given n is 1 positive integer. Example 1: Input: 2 Output: 2 Explanation: There are two ways to climb to the top of the building. 1. Order 1 + Order 2. Order 2 Example 2: Input: 3 output: 3 Explanation: There are 3 ways to climb to the roof. 1. Order 1 + order 1 + order 1 2. Order 1 + order 2 3

This is a classic algorithm to climb stairs.

Their thinking

There are two main ways to solve this problem:

1. Dynamic programming

2. Fibonacci Numbers

Dynamic programming is a relatively important problem solving technique and thinking. In the future, I will write a series of articles that need to use dynamic programming thinking to solve problems, so as to help you better understand dynamic programming.

Let's use Fibonacci to solve this problem.

Fibonacci Numbers, also known as rabbit Numbers, are: 1, 1, 2, 3, 5, 8, 13, 21... In mathematics, its recursive formula is: F(1)=1, F(2)=1, F(n)=F(ES30en-1)+F(ES32en-2) (n ≥ 3, n ∈ N*).

On this topic we can find: 2 stairs moves has two kinds: 1 + 1 order, 2 3 stairs moves has 3 kinds: 1 + 1 order, order 1 + 2, 2 + 1 order 4 flights there are five kinds of moves: order 1 + 1 + 1 + 1 order, order 1 + 2 + 1 order, order 1 + 1 + 2 and 2 + 2 order, 2 + 1 + 1 order...

To sum up, we can find that n staircase has m climbing methods, and m conforms to Fibonacci sequence law, so go straight to the code!

Go implementation

//  Fibonacci sequence 
// 1 1 2 3 5 8 13 ....
func climbStairs2(n int) int {
 // 1  The steps go straight back  1
 if n == 1 {
  return 1
 }
 // 2  The steps go straight back  2
 if n == 2 {
  return 2
 }
 current := 2
 pre := 1
 //  The current step is the sum of the first two steps 
 for i := 3; i <= n;i ++ {
  current = current + pre
  pre = current - pre
 }
 return current
}

PHP implementation, 1 in two versions, see what kind of code you like

function climbStairs($n) {
 // if($n==1) return 1;
 // $dp[1]=1;
 // $dp[2]=2;
 // for($i=3;$i<=$n;$i++){
 //  $dp[$i]=$dp[$i-1]+$dp[$i-2];
 // }
 // 
 // return $dp[$n];

 if($n <= 2) return $n;
 $dp = [1 => 1,2 => 2];
 foreach(range(3,$n+1) as $v){
  // Recursive addition, this stair climbing is the end of fiborach's algorithm f(n-1)+f(n-2) And of the 
  $dp[$v] = $dp[$v-1] + $dp[$v-2]; 
 }

 return $dp[$n];
}

conclusion