Posted on by Kalkicode
Code Dynamic Programming

# Climbing stairs using dynamic programming

When faced with a problem of climbing stairs with various jump options, dynamic programming can provide an efficient solution. This article presents an implementation in C that utilizes dynamic programming to determine the number of possible ways to climb a given number of stairs using different jump sizes.

## Problem Statement

The problem can be defined as follows: You are standing at the bottom of a staircase with `s` stairs, and you can climb the stairs using a set of pre-defined jump sizes. Each jump size represents the number of stairs you can climb at once. The goal is to find the total number of distinct ways you can reach the top of the staircase.

## Algorithm

The algorithm for solving this problem using dynamic programming is as follows:

1. Create an array `dp` of size `s + 1` to store the number of ways to reach each stair.
2. Initialize `dp[0]` and `dp[1]` as 1 since there is only one way to reach the first and second stairs.
3. Iterate over the remaining stairs from index 2 up to `s`.
4. For each stair, initialize `dp[i]` as 0.
5. For each possible jump size `j`, from 1 up to the maximum jump size and as long as `j` is less than or equal to `i`:
• Update `dp[i]` by adding the number of ways to reach the previous stair `(dp[i - j])`.
6. After the iteration, the value of `dp[s]` will represent the total number of distinct ways to reach the top of the staircase.

## Code Implementation

``````// C Program
// Climbing stairs using dynamic programming
#include <stdio.h>

void possibleMove(int s, int jump)
{
if (s <= 0 || jump <= 0)
{
return;
}
int dp[s + 1];
// initial moves
dp[0] = 1;
dp[1] = 1;
for (int i = 2; i <= s; ++i)
{
dp[i] = 0;
for (int j = 1; j <= jump && j <= i; ++j)
{
// Update value
dp[i] = dp[i] + dp[i - j];
}
}
printf("\n Stairs : %d, Jumps : %d", s, jump);
printf("\n Result : %d", dp[s]);
}
int main()
{
int s = 5;
int jump = 2;
// Test
possibleMove(s, jump);
return 0;
}``````

#### Output

`````` Stairs : 5, Jumps : 2
Result : 8``````
``````/*
Java Program for
Climbing stairs using dynamic programming
*/
public class Climbing
{
public void possibleMove(int s, int jump)
{
if (s <= 0 || jump <= 0)
{
return;
}
int[] dp = new int[s + 1];
// initial moves
dp[0] = 1;
dp[1] = 1;
for (int i = 2; i <= s; ++i)
{
dp[i] = 0;
for (int j = 1; j <= jump && j <= i; ++j)
{
// Update value
dp[i] = dp[i] + dp[i - j];
}
}
System.out.print("\n Stairs : " + s + ", Jumps : " + jump);
System.out.print("\n Result : " + dp[s]);
}
public static void main(String[] args)
{
Climbing task = new Climbing();
int s = 5;
int jump = 2;
// Test
}
}``````

#### Output

`````` Stairs : 5, Jumps : 2
Result : 8``````
``````// Include header file
#include <iostream>

using namespace std;
/*
C++ Program for
Climbing stairs using dynamic programming
*/
class Climbing
{
public: void possibleMove(int s, int jump)
{
if (s <= 0 || jump <= 0)
{
return;
}
int *dp = new int[s + 1];
// initial moves
dp[0] = 1;
dp[1] = 1;
for (int i = 2; i <= s; ++i)
{
dp[i] = 0;
for (int j = 1; j <= jump && j <= i; ++j)
{
// Update value
dp[i] = dp[i] + dp[i - j];
}
}
cout << "\n Stairs : " << s << ", Jumps : " << jump;
cout << "\n Result : " << dp[s];
}
};
int main()
{
Climbing *task = new Climbing();
int s = 5;
int jump = 2;
// Test
return 0;
}``````

#### Output

`````` Stairs : 5, Jumps : 2
Result : 8``````
``````// Include namespace system
using System;
/*
Csharp Program for
Climbing stairs using dynamic programming
*/
public class Climbing
{
public void possibleMove(int s, int jump)
{
if (s <= 0 || jump <= 0)
{
return;
}
int[] dp = new int[s + 1];
// initial moves
dp[0] = 1;
dp[1] = 1;
for (int i = 2; i <= s; ++i)
{
dp[i] = 0;
for (int j = 1; j <= jump && j <= i; ++j)
{
// Update value
dp[i] = dp[i] + dp[i - j];
}
}
Console.Write("\n Stairs : " + s + ", Jumps : " + jump);
Console.Write("\n Result : " + dp[s]);
}
public static void Main(String[] args)
{
Climbing task = new Climbing();
int s = 5;
int jump = 2;
// Test
}
}``````

#### Output

`````` Stairs : 5, Jumps : 2
Result : 8``````
``````package main
import "fmt"
/*
Go Program for
Climbing stairs using dynamic programming
*/

func possibleMove(s, jump int) {
if s <= 0 || jump <= 0 {
return
}
var dp = make([] int, s + 1)
// initial moves
dp[0] = 1
dp[1] = 1
for i := 2 ; i <= s ; i++ {
dp[i] = 0
for j := 1 ; j <= jump && j <= i ; j++ {
// Update value
dp[i] = dp[i] + dp[i - j]
}
}
fmt.Print("\n Stairs : ", s, ", Jumps : ", jump)
fmt.Print("\n Result : ", dp[s])
}
func main() {
var s int = 5
var jump int = 2
// Test
possibleMove(s, jump)
}``````

#### Output

`````` Stairs : 5, Jumps : 2
Result : 8``````
``````<?php
/*
Php Program for
Climbing stairs using dynamic programming
*/
class Climbing
{
public	function possibleMove(\$s, \$jump)
{
if (\$s <= 0 || \$jump <= 0)
{
return;
}
\$dp = array_fill(0, \$s + 1, 0);
// initial moves
\$dp[0] = 1;
\$dp[1] = 1;
for (\$i = 2; \$i <= \$s; ++\$i)
{
for (\$j = 1; \$j <= \$jump && \$j <= \$i; ++\$j)
{
// Update value
\$dp[\$i] = \$dp[\$i] + \$dp[\$i - \$j];
}
}
echo("\n Stairs : ".\$s.", Jumps : ".\$jump);
echo("\n Result : ".\$dp[\$s]);
}
}

function main()
{
\$task = new Climbing();
\$s = 5;
\$jump = 2;
// Test
}
main();``````

#### Output

`````` Stairs : 5, Jumps : 2
Result : 8``````
``````/*
Node JS Program for
Climbing stairs using dynamic programming
*/
class Climbing
{
possibleMove(s, jump)
{
if (s <= 0 || jump <= 0)
{
return;
}
var dp = Array(s + 1).fill(0);
// initial moves
dp[0] = 1;
dp[1] = 1;
for (var i = 2; i <= s; ++i)
{
for (var j = 1; j <= jump && j <= i; ++j)
{
// Update value
dp[i] = dp[i] + dp[i - j];
}
}
process.stdout.write("\n Stairs : " + s + ", Jumps : " + jump);
process.stdout.write("\n Result : " + dp[s]);
}
}

function main()
{
var task = new Climbing();
var s = 5;
var jump = 2;
// Test
}
main();``````

#### Output

`````` Stairs : 5, Jumps : 2
Result : 8``````
``````#    Python 3 Program for
#    Climbing stairs using dynamic programming
class Climbing :
def possibleMove(self, s, jump) :
if (s <= 0 or jump <= 0) :
return

dp = [0] * (s + 1)
#  initial moves
dp[0] = 1
dp[1] = 1
i = 2
while (i <= s) :
j = 1
while (j <= jump and j <= i) :
#  Update value
dp[i] = dp[i] + dp[i - j]
j += 1

i += 1

print("\n Stairs : ", s ,", Jumps : ", jump, end = "")
print("\n Result : ", dp[s], end = "")

def main() :
s = 5
jump = 2
#  Test

if __name__ == "__main__": main()``````

#### Output

`````` Stairs :  5 , Jumps :  2
Result :  8``````
``````#    Ruby Program for
#    Climbing stairs using dynamic programming
class Climbing
def possibleMove(s, jump)
if (s <= 0 || jump <= 0)
return
end

dp = Array.new(s + 1) {0}
#  initial moves
dp[0] = 1
dp[1] = 1
i = 2
while (i <= s)
j = 1
while (j <= jump && j <= i)
#  Update value
dp[i] = dp[i] + dp[i - j]
j += 1
end

i += 1
end

print("\n Stairs : ", s ,", Jumps : ", jump)
print("\n Result : ", dp[s])
end

end

def main()
s = 5
jump = 2
#  Test
end

main()``````

#### Output

`````` Stairs : 5, Jumps : 2
Result : 8``````
``````/*
Scala Program for
Climbing stairs using dynamic programming
*/
class Climbing()
{
def possibleMove(s: Int, jump: Int): Unit = {
if (s <= 0 || jump <= 0)
{
return;
}
var dp: Array[Int] = Array.fill[Int](s + 1)(0);
// initial moves
dp(0) = 1;
dp(1) = 1;
var i: Int = 2;
while (i <= s)
{
var j: Int = 1;
while (j <= jump && j <= i)
{
// Update value
dp(i) = dp(i) + dp(i - j);
j += 1;
}
i += 1;
}
print("\n Stairs : " + s + ", Jumps : " + jump);
print("\n Result : " + dp(s));
}
}
object Main
{
def main(args: Array[String]): Unit = {
var task: Climbing = new Climbing();
var s: Int = 5;
var jump: Int = 2;
// Test
}
}``````

#### Output

`````` Stairs : 5, Jumps : 2
Result : 8``````
``````/*
Swift 4 Program for
Climbing stairs using dynamic programming
*/
class Climbing
{
func possibleMove(_ s: Int, _ jump: Int)
{
if (s <= 0 || jump <= 0)
{
return;
}
var dp: [Int] = Array(repeating: 0, count: s + 1);
// initial moves
dp[0] = 1;
dp[1] = 1;
var i: Int = 2;
while (i <= s)
{
var j: Int = 1;
while (j <= jump && j <= i)
{
// Update value
dp[i] = dp[i] + dp[i - j];
j += 1;
}
i += 1;
}
print("\n Stairs : ", s ,", Jumps : ", jump, terminator: "");
print("\n Result : ", dp[s], terminator: "");
}
}
func main()
{
let task: Climbing = Climbing();
let s: Int = 5;
let jump: Int = 2;
// Test
}
main();``````

#### Output

`````` Stairs :  5 , Jumps :  2
Result :  8``````
``````/*
Kotlin Program for
Climbing stairs using dynamic programming
*/
class Climbing
{
fun possibleMove(s: Int, jump: Int): Unit
{
if (s <= 0 || jump <= 0)
{
return;
}
var dp: Array < Int > = Array(s + 1)
{
0
};
// initial moves
dp[0] = 1;
dp[1] = 1;
var i: Int = 2;
while (i <= s)
{
var j: Int = 1;
while (j <= jump && j <= i)
{
// Update value
dp[i] = dp[i] + dp[i - j];
j += 1;
}
i += 1;
}
print("\n Stairs : " + s + ", Jumps : " + jump);
print("\n Result : " + dp[s]);
}
}
fun main(args: Array < String > ): Unit
{
val task: Climbing = Climbing();
val s: Int = 5;
val jump: Int = 2;
// Test
}``````

#### Output

`````` Stairs : 5, Jumps : 2
Result : 8``````

## Output Explanation

When running the provided code with `s = 5` and `jump = 2`, the output is as follows:

``````
Stairs: 5, Jumps: 2
Result: 8
``````

This output indicates that there are 8 distinct ways to climb a staircase with 5 stairs using jump sizes of 1 or 2.

## Time Complexity

The time complexity of the climbing stairs algorithm using dynamic programming is `O(s * jump)`, where `s` represents the number of stairs and `jump` represents the maximum jump size. The algorithm requires iterating over each stair and performing a nested loop for each possible jump size.

## Finally

The climbing stairs problem can be efficiently solved using dynamic programming. By breaking down the problem into smaller subproblems and storing the results in an array, the algorithm can determine the total number of distinct ways to climb a staircase using various jump sizes. The provided C implementation demonstrates this approach, and the explained output clarifies the result. Understanding the time complexity helps to evaluate the efficiency of the algorithm for different inputs.

## Comment

Please share your knowledge to improve code and content standard. Also submit your doubts, and test case. We improve by your feedback. We will try to resolve your query as soon as possible.

Categories
Relative Post