Write a program to calculate the number of ways to climb stairs in Python

Problem : Given n stairs, a person standing at the bottom of the stairs wants to climb to the top. This person can take 1 step or 2 steps at a time. Count the number of ways he or she can get to the top.

You can see an example in the picture. The value of n is 3 and there are 3 ways to step to the top.

For example:

Input: n = 1 Output: 1 There is only one way to climb 1 stair Input: n = 2 Output: 2 There are two ways: (1, 1) and (2) Input: n = 4 Output: 5 (1, 1, 1, 1), (1, 1, 2), (2, 1, 1), (1, 2, 1), (2, 2) 

In this article, TipsMake.com will learn with you how to write a program to count the number of ways to climb stairs in Python.

Method 1: We will use recursion to solve this problem

We can easily see the recursion in this problem. The person can get to the nth step from the n-1th step or the n-2th step. Therefore, for each of the nth steps, let's try to find the number of ways to get to the n-1 and n-2th rungs and add them to give the answer to the nth rung. With this approach, we have the following expression:

ways(n) = ways(n-1) + ways(n-2)

The above expression is actually an expression of Fibonacci numbers but one thing to note is that the value of ways(n) is equal to fibonacci(n+1).

ways(1) = fib(2) = 1 ways(2) = fib(3) = 2 ways(3) = fib(4) = 3

To better understand, let's refer to the recursion tree below:

Input: N = 4 fib(5) '3' / '2' / fib(4) fib(3) '2' / '1' / / / fib(3) fib(2)fib(2) fib(1) / '1' / '0' '1' / '1' / / fib(1) fib(0) fib(2) fib(1)

So we can use the function for Fibonacci numbers to find the value of ways(n). Here is sample code:

# Python program to count # ways to reach nth stair # Recursive function to find # Nth fibonacci number def fib(n): if n <= 1: return n return fib(n-1) + fib(n-2) # Returns no. of ways to # reach sth stair def countWays(s): return fib(s + 1) # Driver program s = 4 print "Số cách là = ", print countWays(s) # Contributed by Harshit Agrawal

Generalizing the problem

How to count the number of ways if a person can climb m stairs for a given number of m. For example m is 4, then the person can climb 1 ladder, 2 stairs, 3 stairs or 4 stairs at the same time.

To generalize the above approach, we can use the following recursive relation:

ways(n, m) = ways(n-1, m) + ways(n-2, m) + . ways(n-m, m) 

In this approach, to get to the nth stair, try to climb all the stairs less n than the current stairs.

Here is sample code for this overview:

# A program to count the number of ways # to reach n'th stair # Recursive function used by countWays def countWaysUtil(n, m): if n <= 1: return n res = 0 i = 1 while i<= m and i<= n: res = res + countWaysUtil(n-i, m) i = i + 1 return res # Returns number of ways to reach s'th stair def countWays(s, m): return countWaysUtil(s + 1, m) # Driver program s, m = 4, 2 print "Số cách là =", countWays(s, m) # Contributed by Harshit Agrawal

Method 2: Memorize

We can also use dp's bottom-up approach to solve this problem.

We can create an array dp[] and initialize it with -1.

Whenever we see that a subproblem is not solved, we can call the method recursively.

Otherwise, we stop the recursion if the subproblem is solved.

The sample code is as follows:

# Python program to count number of # ways to reach Nth stair # A simple recursive program to # find N'th fibonacci number def fib(n, dp): if (n <= 1): return 1 if(dp[n] != -1 ): return dp[n] dp[n] = fib(n - 1, dp) + fib(n - 2, dp) return dp[n] # Returns number of ways to # reach s'th stair def countWays(n): dp = [-1 for i in range(n + 1)] fib(n, dp) return dp[n] # Driver Code n = 4 print("Số cách là = " + str(countWays(n))) # This code is contributed by shinjanpatra

Method 3: Dynamic Programming

This way uses Dynamic Programming technique to solve the problem.

We create a res[] table in a bottom-up manner using the following relationship:

res[i] = res[i] + res[i-j] for every (i-j) >= 0

Thus, the i-th index of the array will contain the number of ways needed to step to the i-th order taking into account all possible climbs (i.e. from 1 to i).

Here is sample code following this approach:

# A program to count the number of # ways to reach n'th stair # Recursive function used by countWays def countWaysUtil(n, m): # Creates list res with all elements 0 res = [0 for x in range(n)] res[0], res[1] = 1, 1 for i in range(2, n): j = 1 while j<= m and j<= i: res[i] = res[i] + res[i-j] j = j + 1 return res[n-1] # Returns number of ways to reach s'th stair def countWays(s, m): return countWaysUtil(s + 1, m) # Driver Program s, m = 4, 2 print "Số cách là =", countWays(s, m) # Contributed by Harshit Agrawal

Method 4: Using Sliding Windows

In this way, we will use the Dymanic Programming Approach more effectively.

In this approach for the ith staircase, we keep a window containing the total number of final m stairs from which we can climb the ith staircase. Instead of running an inner loop, we persist the result of the loop inside a temporary variable. We remove the elements of the previous window and add the element of the current window.

Here is sample code:

# Python3 program to count the number # of ways to reach n'th stair when # user climb 1 . m stairs at a time. # Function to count number of ways # to reach s'th stair def countWays(n, m): temp = 0 res = [1] for i in range(1, n + 1): s = i - m - 1 e = i - 1 if (s >= 0): temp -= res[s] temp += res[e] res.append(temp) return res[n] # Driver Code n = 5 m = 3 print('Số cách là =', countWays(n, m)) # This code is contributed by 31ajaydandge

Method 5: Use simple math

In this approach, we simply count the number of sets with 2. This method is only applicable if the ordering problem during step counting is not important.

# Here n/2 is done to count the number 2's in n # 1 is added for case where there is no 2. # eg: if n=4 ans will be 3. # {1,1,1,1} set having no 2. # {1,1,2} ans {2,2} (n/2) sets containing 2. print("Number of ways when order " "of steps does not matter is : ", 1 + (n // 2)) # This code is contributed by rohitsingh07052

Method 6: Use the Matrix Exponentitation technique

In this way, we use Matrix Exponentitation technique to solve the problem.

The number of ways to step up the nth ladder (with consideration of the order) is equal to the sum of the number of ways to step up and turn on the n-1th ladder and the n-2th step.

This corresponds to the following repetition relationship:

f(n) = f(n-1) + f(n-2) f(1) = 1 f(2) = 2

where f(n) is the number of steps to the nth step.

Note:

f(1) = 1 vì chỉ có 1 cách bước lên đỉnh cầu thang có 1 bậc, n=1, {1} f(2) = 2 vì chỉ có 2 cách bước lên đỉnh cầu thang có 1 bậc, n=2, {1,1},{2}

It is a kind of linear recurrence relation with constant coefficients and we can solve them by matrix exponentiation method. Basically, this method finds the transformation matrix for a given recurrence relation and iteratively applies this transformation to a basis vector to find the solution.

F(n) = CN-1F(1)

where C is the transformation matrix, F(1) is the basis vector, and F(n) is the desired solution.

Therefore, in our case the matrix C will be:

0 1 1 1

C ^N-1  can be computed using the Divide and Conquer technique, in O((K^3) Log n) where K is the size of C.

And F(1):

1 2

For example, for n=4:

F(4) = C ³ F(1)

C ³ =

1 2 2 3

Therefore, C ³ F(1) =

5 8

The sample code is as follows:

# Computes A*B # where A,B are square matrices def mul(A, B, MOD): K = len(A); C = [[0 for i in range(K)] for j in range(K)] ; for i in range(1, K): for j in range(1, K): for k in range(1, K): C[i][j] = (C[i][j] + A[i][k] * B[k][j]) % MOD; return C; # Computes A^n def power( A, n): if (n == 1): return A; if (n % 2 != 0): # n is odd # A^n = A * [ A^(n-1) ] A = mul(A, power(A, n - 1), 1000000007); else: # n is even # A^n = [ A^(n/2) ] * [ A^(n/2) ] A = power(A, n // 2); A = mul(A, A, 1000000007); return A; def ways(n): F = [0 for i in range(3)]; F[1] = 1; F[2] = 2; K = 2; MOD = 1000000007; # create K*K matrix C = [[0 for i in range(K+1)] for j in range(K+1)]; ''' * A matrix with (i+1)th element as 1 and last row contains constants [ [0 1 0 0 * . 0] [0 0 1 0 . 0] [0 0 0 1 . 0] [. . . . . .] [. . . . . .] [c(k) * c(k-1) c(k-2) . c1] ] ''' for i in range(1,K): C[i][i + 1] = 1; # Last row is the constants c(k) c(k-1) . c1 # f(n) = 1*f(n-1) + 1*f(n-2) C[K][1] = 1; C[K][2] = 1; if (n <= 2): return F[n]; # f(n) = C^(n-1)*F C = power(C, n - 1); result = 0; # result will be the first row of C^(n-1)*F for i in range(1,K+1): result = (result + C[1][i] * F[i]) % MOD; return result; # Driver code if __name__ == '__main__': n = 4; print("Số cách là = " , ways(n) , ""); # This code is contributed by gauravrajput1

Generalizing the problem

Given an array A{a1, a2, ., am} containing all valid steps, calculate the number of steps required to step up the nth, ordered ladder.

For example:

Input: A = [1,2] n = 4 Output: 5 Giải thích: Tìm số cách để leo lên bậc thang thứ 4, mỗi lần có thể leo 1 hoặc 2 bước. Số cách là: {1,1,1,1} {1,1,2} {1,2,1} {2,1,1} {2,2} = 5 Input: A = [2,4,5] n = 9 Output: 5 Giải thích: Có 5 cách để leo lên bậc thang thứ 9 với khả năng leo 2 hoặc 4 hoặc 5 bậc thang mỗi lần. Số cách là: {5,4} {4,5} {2,2,5} {2,5,2} {5,2,2} = 5 

The number of ways to climb to the nth step is given by the following recursion relation:

Let K be the largest element in A.

Step 1: Calculate the basis vector F(1) (including f(1). f(K))

It can be done in O(m2K) time using the following dynamic programming approach:

Let's flip A = {2,4,5] as an example. To compute F(1) = {f(1), f(2), f(3), f(4), f(5)}, we will maintain an initial empty array and iteratively concatenate Ai with it and for each Ai we will find the number of ways to achieve [Ai-1, to Ai].

Therefore, for A = {2, 4, 5]

Let T be the original empty array:

Iteration 1: T = {2} n = {1,2} dp = {0,1} (Number of ways to reach n=1,2 with steps given by T) Iteration 2: T = {2,4} n = {1,2,3,4} dp = {0,1,0,2} (Number of ways to reach n=1,2,3,4 with steps given by T) Iteration 3: T = {2,4,5} n = {1,2,3,4,5} dp = {0,1,0,2,1} (Number of ways to reach n=1,2,3,4,5 with steps given by T)

Note: since some values ​​are already calculated (1,2 for iteration 2.) we can avoid them in the loop.

After all iterations the dp array will be: [0,1,0,2,1]

So the basis vector F(1) for A = [2,4,5] is:

0 1 0 2 1

Now that we have the basis vector F(1), it's pretty easy to compute C (the transformation matrix).

Step 2: Calculate C, transformation matrix

It's a matrix with elements Ai, i+1 = 1 and the last row contains constants.

Now, constants can be determined by the presence of that element in A.

So for A = [2,4,5] the constants will be c = [1,1,0,1,0] (Ci = 1 if K-i+1) is present in A, or 0 if 1 <= i <= K.

Therefore, the transformation matrix C for A = [2,4,5] is:

0 1 0 0 0 0 0 1 0 0 0 0 0 1 0 0 0 0 0 1 1 1 0 1 0

Step 3: Calculate F(n)

To calculate F(n), the following formula is used:

F(n) - Cn-1F(1)

Now that we have C and F(1), we can use the Divide and Conquer technique to find C ^n-1 and from there find the output.

Here is sample code:

# Computes A*B when A,B are square matrices of equal # dimensions) def mul(A, B, MOD): K = len(A); C = [[0 for i in range(K)] for j in range(K)] ; for i in range(1, K): for j in range(1, K): for k in range(1, K): C[i][j] = (C[i][j] + A[i][k] * B[k][j]) % MOD; return C; def power(A, n): if (n == 1): return A; if (n % 2 != 0): # n is odd # A^n = A * [ A^(n-1) ] A = mul(A, power(A, n - 1), 1000000007); else: # n is even # A^n = [ A^(n/2) ] * [ A^(n/2) ] A = power(A, n // 2); A = mul(A, A, 1000000007); return A; def initialize(A): # Initializes the base vector F(1) K = A[len(A)-1]; # Assuming A is sorted F = [0 for i in range(K+1)]; dp = [0 for i in range(K+1)]; dp[0] = 0; dp[A[1]] = 1; # There is one and only one way to reach # first element F[A[1]] = 1; for i in range(2,len(A)): # Loop through A[i-1] to A[i] and fill the dp array for j in range(A[i - 1] + 1,A[i]+1): # dp[j] = dp[j-A[0]] + . + dp[j-A[i-1]] for k in range(1,i): dp[j] += dp[j - A[k]]; # There will be one more way to reach A[i] dp[A[i]] += 1; F[A[i]] = dp[A[i]]; return F; def ways(A, n): K = A[len(A) - 1]; # Assuming A is sorted F = initialize(A); # O(m^2*K) MOD = 1000000007; # create K*K matrix C = [[0 for i in range(K+1)] for j in range(K+1)]; ''' * A matrix with (i+1)th element as 1 and last row contains constants [ [0 1 0 0 * . 0] [0 0 1 0 . 0] [0 0 0 1 . 0] [. . . . . .] [. . . . . .] [c(k) * c(k-1) c(k-2) . c1] ] ''' for i in range(1,K): C[i][i + 1] = 1; # Last row is the constants c(k) c(k-1) . c1 # f(n) = 1*f(n-1) + 1*f(n-2) for i in range(1, len(A)): C[K][K - A[i] + 1] = 1; if (n <= K): return F[n]; # F(n) = C^(n-1)*F C = power(C, n - 1); # O(k^3Log(n)) result = 0; # result will be the first row of C^(n-1)*F for i in range(1, K+1): result = (result + C[1][i] * F[i]) % MOD; return result; # Driver code if __name__ == '__main__': n = 9; A = [ 0, 2, 4, 5] ; # 0 is just because we are using 1 based indexing print("Số lượng cách là = " ,ways(A, n)); # This code is contributed by gauravrajput1

Note : This approach is ideal when n is too large to use loops.

Example : You should consider this approach when 1<= n <= 109 and 1 <= m,k <= 102.

Hope this article will be useful to you.