Dadas N cajas de dimensión unitaria, es decir (1×1 
). La tarea es encontrar el número total de escaleras diferentes que se pueden hacer a partir de esas cajas con las siguientes reglas:
- La escalera debe estar en estricto orden descendente.
- Cada escalera contiene al menos dos escalones. (Los escalones totales son iguales al ancho de la escalera).
Ejemplos :
Entrada : N = 5
Salida : 2
Las dos escaleras son las siguientes:
Entrada : N = 6
Salida : 3
Las tres escaleras son las siguientes:
Si consideramos el total de pasos = 2, podemos observar el hecho de que el número de escaleras se incrementa en 1 si N se incrementa en 2. Podemos ilustrar lo anterior con la siguiente imagen:
Ahora, si el total de pasos es mayor que 2 (supongamos, el total de pasos = K), entonces podemos tomar esto como primero crear una base (la base requiere cajas iguales al total de pasos) para la escalera y poner otra escalera sobre ella de los pasos de tamaño K y K – 1 tienen casillas N – K. (porque las casillas K ya se usaron para crear la base). Por lo tanto, podemos resolver este problema usando programación dinámica de abajo hacia arriba.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program to find the total number of
// different staircase that can made
// from N boxes
#include <iostream>
using namespace std;
// Function to find the total number of
// different staircase that can made
// from N boxes
int countStaircases(int N)
{
// DP table, there are two states.
// First describes the number of boxes
// and second describes the step
int memo[N + 5][N + 5];
// Initialize all the elements of
// the table to zero
for (int i = 0; i <= N; i++) {
for (int j = 0; j <= N; j++) {
memo[i][j] = 0;
}
}
// Base case
memo[3][2] = memo[4][2] = 1;
for (int i = 5; i <= N; i++) {
for (int j = 2; j <= i; j++) {
// When step is equal to 2
if (j == 2) {
memo[i][j] = memo[i - j][j] + 1;
}
// When step is greater than 2
else {
memo[i][j] = memo[i - j][j] +
memo[i - j][j - 1];
}
}
}
// Count the total staircase
// from all the steps
int answer = 0;
for (int i = 1; i <= N; i++)
answer = answer + memo[N][i];
return answer;
}
// Driver Code
int main()
{
int N = 7;
cout << countStaircases(N);
return 0;
}
Java
// Java program to find the total number of
// different staircase that can made
// from N boxes
import java.util.*;
class GFG
{
// Function to find the total number of
// different staircase that can made
// from N boxes
static int countStaircases(int N)
{
// DP table, there are two states.
// First describes the number of boxes
// and second describes the step
int [][] memo=new int[N + 5][N + 5];
// Initialize all the elements of
// the table to zero
for (int i = 0; i <= N; i++) {
for (int j = 0; j <= N; j++) {
memo[i][j] = 0;
}
}
// Base case
memo[3][2] = memo[4][2] = 1;
for (int i = 5; i <= N; i++) {
for (int j = 2; j <= i; j++) {
// When step is equal to 2
if (j == 2) {
memo[i][j] = memo[i - j][j] + 1;
}
// When step is greater than 2
else {
memo[i][j] = memo[i - j][j] +
memo[i - j][j - 1];
}
}
}
// Count the total staircase
// from all the steps
int answer = 0;
for (int i = 1; i <= N; i++)
answer = answer + memo[N][i];
return answer;
}
// Driver Code
public static void main(String [] args)
{
int N = 7;
System.out.println(countStaircases(N));
}
}
// This code is contributed
// by ihritik
Python 3
# Python 3 program to find the total # number of different staircase that # can made from N boxes # Function to find the total number # of different staircase that can # made from N boxes def countStaircases(N): # DP table, there are two states. # First describes the number of boxes # and second describes the step memo = [[0 for x in range(N + 5)] for y in range(N + 5)] # Initialize all the elements of # the table to zero for i in range(N + 1): for j in range (N + 1): memo[i][j] = 0 # Base case memo[3][2] = memo[4][2] = 1 for i in range (5, N + 1) : for j in range (2, i + 1) : # When step is equal to 2 if (j == 2) : memo[i][j] = memo[i - j][j] + 1 # When step is greater than 2 else : memo[i][j] = (memo[i - j][j] + memo[i - j][j - 1]) # Count the total staircase # from all the steps answer = 0 for i in range (1, N + 1): answer = answer + memo[N][i] return answer # Driver Code if __name__ == "__main__": N = 7 print (countStaircases(N)) # This code is contributed # by ChitraNayal
C#
// C# program to find the total number
// of different staircase that can made
// from N boxes
using System;
class GFG
{
// Function to find the total number
// of different staircase that can
// made from N boxes
static int countStaircases(int N)
{
// DP table, there are two states.
// First describes the number of boxes
// and second describes the step
int [,] memo = new int[N + 5, N + 5];
// Initialize all the elements
// of the table to zero
for (int i = 0; i <= N; i++)
{
for (int j = 0; j <= N; j++)
{
memo[i, j] = 0;
}
}
// Base case
memo[3, 2] = memo[4, 2] = 1;
for (int i = 5; i <= N; i++)
{
for (int j = 2; j <= i; j++)
{
// When step is equal to 2
if (j == 2)
{
memo[i, j] = memo[i - j, j] + 1;
}
// When step is greater than 2
else
{
memo[i, j] = memo[i - j, j] +
memo[i - j, j - 1];
}
}
}
// Count the total staircase
// from all the steps
int answer = 0;
for (int i = 1; i <= N; i++)
answer = answer + memo[N, i];
return answer;
}
// Driver Code
public static void Main()
{
int N = 7;
Console.WriteLine(countStaircases(N));
}
}
// This code is contributed
// by Subhadeep
PHP
<?php
// PHP program to find the total
// number of different staircase
// that can made from N boxes
// Function to find the total
// number of different staircase
// that can made from N boxes
function countStaircases($N)
{
// Initialize all the elements
// of the table to zero
for ($i = 0; $i <= $N; $i++)
{
for ($j = 0; $j <= $N; $j++)
{
$memo[$i][$j] = 0;
}
}
// Base case
$memo[3][2] = $memo[4][2] = 1;
for ($i = 5; $i <= $N; $i++)
{
for ($j = 2; $j <= $i; $j++)
{
// When step is equal to 2
if ($j == 2)
{
$memo[$i][$j] = $memo[$i - $j][$j] + 1;
}
// When step is greater than 2
else
{
$memo[$i][$j] = $memo[$i - $j][$j] +
$memo[$i - $j][$j - 1];
}
}
}
// Count the total staircase
// from all the steps
$answer = 0;
for ($i = 1; $i <= $N; $i++)
$answer = $answer + $memo[$N][$i];
return $answer;
}
// Driver Code
$N = 7;
echo countStaircases($N);
// This code is contributed
// by Shivi_Aggarwal
?>
Javascript
<script>
// Javascript program to find the total number of
// different staircase that can made
// from N boxes
// Function to find the total number of
// different staircase that can made
// from N boxes
function countStaircases(N)
{
// DP table, there are two states.
// First describes the number of boxes
// and second describes the step
let memo=new Array(N + 5);
for(let i=0;i<N+5;i++)
{
memo[i]=new Array(N+5);
for(let j=0;j<N+5;j++)
{
memo[i][j]=0;
}
}
// Initialize all the elements of
// the table to zero
for (let i = 0; i <= N; i++) {
for (let j = 0; j <= N; j++) {
memo[i][j] = 0;
}
}
// Base case
memo[3][2] = memo[4][2] = 1;
for (let i = 5; i <= N; i++) {
for (let j = 2; j <= i; j++) {
// When step is equal to 2
if (j == 2) {
memo[i][j] = memo[i - j][j] + 1;
}
// When step is greater than 2
else {
memo[i][j] = memo[i - j][j] +
memo[i - j][j - 1];
}
}
}
// Count the total staircase
// from all the steps
let answer = 0;
for (let i = 1; i <= N; i++)
answer = answer + memo[N][i];
return answer;
}
// Driver Code
let N = 7;
document.write(countStaircases(N));
// This code is contributed by rag2127
</script>
Producción:
4
Complejidad de Tiempo : O( 
).
Publicación traducida automáticamente
Artículo escrito por sauravchandra1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA