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:
- Create an array
dp
of sizes + 1
to store the number of ways to reach each stair. - Initialize
dp[0]
anddp[1]
as 1 since there is only one way to reach the first and second stairs. - Iterate over the remaining stairs from index 2 up to
s
. - For each stair, initialize
dp[i]
as 0. - For each possible jump size
j
, from 1 up to the maximum jump size and as long asj
is less than or equal toi
: - Update
dp[i]
by adding the number of ways to reach the previous stair(dp[i - j])
. - 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
task.possibleMove(s, jump);
}
}
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
task->possibleMove(s, jump);
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
task.possibleMove(s, jump);
}
}
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
$task->possibleMove($s, $jump);
}
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
task.possibleMove(s, jump);
}
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() :
task = Climbing()
s = 5
jump = 2
# Test
task.possibleMove(s, jump)
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()
task = Climbing.new()
s = 5
jump = 2
# Test
task.possibleMove(s, jump)
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
task.possibleMove(s, jump);
}
}
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
task.possibleMove(s, jump);
}
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
task.possibleMove(s, jump);
}
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.
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.
New Comment