Climbing Stairs Problem using Dynamic Programming (Memoization)
The above recursive solution has Optimal Substructure and Overlapping Subproblems so Dynamic programming (Memoization) can be used to solve the problem. So a 1D array can be used to store results of previously solved subproblems.
Follow the below steps to Implement the idea:
- Create a 1D dp where dp[i] represent the number of ways to reach the ith stair from the bottom.
- Check if answer for subproblem already exist or not in dp.
- Recursively call for subproblems and store their result in dp (i.e, dp[n] = countWays(n – 1, dp) + countWays(n – 2, dp)).
- Finally, return dp[n], as it will store the answer for input n.
Below is the implementation of the above approach:
// C++ program to count number of ways to reach Nth stair
#include <bits/stdc++.h>
using namespace std;
// A simple recursive function to find number of ways to
// reach the nth stair
int countWays(int n, int dp[])
{
if (n <= 1)
return dp[n] = 1;
if (dp[n] != -1) {
return dp[n];
}
dp[n] = countWays(n - 1, dp) + countWays(n - 2, dp);
return dp[n];
}
// Driver Code
int main()
{
int n = 4;
int dp[n + 1];
memset(dp, -1, sizeof dp);
cout << "Number of ways = " << countWays(n, dp);
return 0;
}
// C program to count number of ways to reach Nth stair
#include <stdio.h>
#include <string.h>
// A simple recursive function to find number of ways to
// reach the nth stair
int countWays(int n, int dp[])
{
if (n <= 1)
return dp[n] = 1;
if (dp[n] != -1) {
return dp[n];
}
dp[n] = countWays(n - 1, dp) + countWays(n - 2, dp);
return dp[n];
}
// Driver Code
int main()
{
int n = 4;
int dp[n + 1];
memset(dp, -1, sizeof dp);
printf("Number of ways = %d", countWays(n, dp));
return 0;
}
// Java program to count number of
// ways to reach Nth stair
class GFG {
// A simple recursive function to find number of ways to
// reach the nth stair
static int countWays(int n, int dp[])
{
if (n <= 1)
return dp[n] = 1;
if (dp[n] != -1) {
return dp[n];
}
dp[n] = countWays(n - 1, dp) + countWays(n - 2, dp);
return dp[n];
}
// Driver code
public static void main(String[] args)
{
int n = 4;
int[] dp = new int[n + 1];
for (int i = 0; i < n + 1; i++) {
dp[i] = -1;
}
System.out.println(countWays(n, dp));
}
}
// This code is contributed by Karandeep1234
# Python program to count number of
# ways to reach Nth stair
# A simple recursive function to find number of ways to reach the nth stair
def countWays(n, dp):
if (n <= 1):
return 1
if(dp[n] != -1):
return dp[n]
dp[n] = countWays(n - 1, dp) + countWays(n - 2, dp)
return dp[n]
# Driver Code
n = 4
dp = [-1 for i in range(n + 1)]
print("Number of ways = " + str(countWays(n, dp)))
// C# program to implement
// the above approach
using System;
class GFG {
// A simple recursive function to find number of ways to
// reach the nth stair
static int countWays(int n, int[] dp)
{
if (n <= 1)
return dp[n] = 1;
if (dp[n] != -1) {
return dp[n];
}
dp[n] = countWays(n - 1, dp) + countWays(n - 2, dp);
return dp[n];
}
// Driver Code
public static void Main()
{
int n = 4;
int[] dp = new int[n + 1];
for (int i = 0; i < n + 1; i++) {
dp[i] = -1;
}
Console.Write("Number of ways = "
+ countWays(n, dp));
}
}
// This code is contributed by sanjoy_62.
// A simple recursive function to find number of ways to reach the nth stair
function countWays(n, dp)
{
if (n <= 1)
return dp[n] = 1;
if(dp[n] != -1 ){
return dp[n] ;
}
dp[n] = countWays(n - 1, dp) + countWays(n - 2, dp);
return dp[n] ;
}
// Driver Code
let n = 4;
let dp = new Array(n+1).fill(-1) ;
console.log("Number of ways = " + countWays(n,dp));
Output
Number of ways = 5
Time Complexity: O(n)
Auxiliary Space: O(n)
Climbing Stairs to reach at the top.
There are n stairs, a person standing at the bottom wants to climb stairs to reach the nth stair. The person can climb either 1 stair or 2 stairs at a time, the task is to count the number of ways that a person can reach at the top.
Consider the example shown in the diagram. The value of n is 3. There are 3 ways to reach the top. The diagram is taken from Easier Fibonacci puzzles
Examples:
Input: n = 1
Output: 1 There is only one way to climb 1 stairInput: 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)