Detailed explanation of the idea of implementing stair climbing algorithm based on Go and PHP languages

Climbing-Stairs

Question:

Suppose you are climbing the stairs. You need to reach the roof of the building. You can climb 1 or 2 steps each time. How many different ways do you have to climb to the roof? Note: Given n is a positive integer. Example 1: Input: 2 Output: 2 Explanation: There are two ways to climb to the roof. 1. Order 1 + Order 1 2. Order 2 Example 2: Input: 3 Output: 3 Explanation: There are three ways to climb to the roof. 1. 1st order + 1st order + 1st order 2nd order + 2nd order 3. 2nd order + 1st order Source: Liku

This questionClimb the stairsIt is a classic algorithm problem.

Problem-solving ideas

There are two main solutions to this problem:

1. Dynamic planning

2.Fibonacci sequence

Dynamic planning is a relatively important problem-solving technique and ideas. In the future, I will write a series of articles that require the solution of problem-solving using dynamic planning ideas to help everyone better understand dynamic planning.

We use this questionFibonacci sequenceLet's solve it.

Fibonacci sequence also known asRabbit sequence, refers to: 1, 1, 2, 3, 5, 8, 13, 21,..., mathematically, the recursive formula is: F(1)=1, F(2)=1, F(n)=F(n - 1)+F(n - 2)(n ≥ 3, n ∈ N*).

In this topic we can find:There are 2 ways to walk the second-stage stairs: 1st order + 1st order, 2nd orderThere are 3 ways to walk the third stairs: 1st order + 1st order, 1st order + 2nd order, 2nd order + 1st orderThere are 5 ways to walk the fourth stairs: 1st order + 1st order + 1st order + 1st order, 1st order + 2nd order + 1st order, 1st order + 1st order + 2nd order, 2nd order + 2nd order + 1st order……

In summary, we can find that there are m climbing methods for n-stage stairs, and m meetsFibonacci sequenceRule, so just upload the code!

Go implementation

// Fibonacci sequence// 1 1 2 3 5 8 13 ....
func climbStairs2(n int) int {
 // 1 Steps return directly 1 if n == 1 {
  return 1
 }
 // 2 steps return directly 2 if n == 2 {
  return 2
 }
 current := 2
 pre := 1
 // The current way to walk on the stairs is the sum of the first two steps for i := 3; i &lt;= n;i ++ {
  current = current + pre
  pre = current - pre
 }
 return current
}

PHP implementation, there are two versions of implementation, it depends on which code you like

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

 if($n &lt;= 2) return $n;
 $dp = [1 =&gt; 1,2 =&gt; 2];
 foreach(range(3,$n+1) as $v){
  //Recursive addition, this stair climbing is to find the sum of the last f(n-1)+f(n-2) of the Fibolache algorithm  $dp[$v] = $dp[$v-1] + $dp[$v-2]; 
 }

 return $dp[$n];
}

Summarize

This is the end of this article about the detailed explanation of the ideas of implementing stair climbing algorithms based on Go and PHP languages. For more related contents of Go PHP stair climbing algorithms, please search for my previous articles or continue browsing the related articles below. I hope everyone will support me in the future!

Detailed explanation of the idea of ​​implementing stair climbing algorithm based on Go and PHP languages

Detailed explanation of the idea of implementing stair climbing algorithm based on Go and PHP languages