Skip to main content

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
		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.

Last updated on by Kalkicode




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.

New Comment