Dado N número de escaleras. También dado el número de pasos que se pueden dar como máximo de un salto (K). La tarea es encontrar el número de formas posibles en que uno ( solo considere las combinaciones ) puede subir a la parte superior del edificio en K saltos o menos desde la planta baja.
Ejemplos:
Entrada: N = 5, K = 3
Salida: 5
Para llegar a la escalera número 5 podemos elegir la siguiente combinación de saltos:
1 1 1 1 1
1 1 1 2
1 2 2
1 1 3
2 3
Por lo tanto, la respuesta es 5.
Entrada : N = 29, K = 5
Salida: 603
Sea combo[i] el número de formas de llegar al i-ésimo piso. Por lo tanto, el número de formas de llegar a combo[i] desde combo[j] dando un salto de ij será combo[i] += combo[j]. Así que itere para todos los saltos posibles, y para cada salto posible siga agregando las posibles combinaciones a la array combinada. La respuesta final se almacenará en combo[N].
A continuación se muestra la implementación del enfoque anterior.
C++
// C++ program to reach N-th stair
// by taking a maximum of K leap
#include <bits/stdc++.h>
using namespace std;
int solve(int N, int K)
{
// elements of combo[] stores the no of
// possible ways to reach it by all
// combinations of k leaps or less
int combo[N + 1] = { 0 };
// assuming leap 0 exist and assigning
// its value to 1 for calculation
combo[0] = 1;
// loop to iterate over all
// possible leaps upto k;
for (int i = 1; i <= K; i++) {
// in this loop we count all possible
// leaps to reach the jth stair with
// the help of ith leap or less
for (int j = 0; j <= N; j++) {
// if the leap is not more than the i-j
if (j >= i) {
// calculate the value and
// store in combo[j]
// to reuse it for next leap
// calculation for the jth stair
combo[j] += combo[j - i];
}
}
}
// returns the no of possible number
// of leaps to reach the top of
// building of n stairs
return combo[N];
}
// Driver Code
int main()
{
// N i the no of total stairs
// K is the value of the greatest leap
int N = 29;
int K = 5;
cout << solve(N, K);
return 0;
}
Java
// Java program to reach N-th
// stair by taking a maximum
// of K leap
class GFG
{
static int solve(int N, int K)
{
// elements of combo[] stores
// the no. of possible ways
// to reach it by all combinations
// of k leaps or less
int[] combo;
combo = new int[50];
// assuming leap 0 exist
// and assigning its value
// to 1 for calculation
combo[0] = 1;
// loop to iterate over all
// possible leaps upto k;
for (int i = 1; i <= K; i++)
{
// in this loop we count all
// possible leaps to reach
// the jth stair with the
// help of ith leap or less
for (int j = 0; j <= N; j++)
{
// if the leap is not
// more than the i-j
if (j >= i)
{
// calculate the value and
// store in combo[j] to
// reuse it for next leap
// calculation for the
// jth stair
combo[j] += combo[j - i];
}
}
}
// returns the no of possible
// number of leaps to reach
// the top of building of
// n stairs
return combo[N];
}
// Driver Code
public static void main(String args[])
{
// N i the no of total stairs
// K is the value of the
// greatest leap
int N = 29;
int K = 5;
System.out.println(solve(N, K));
}
}
// This code is contributed
// by ankita_saini
Python 3
# Python3 program to reach N-th stair # by taking a maximum of K leap def solve(N, K) : # elements of combo[] stores the no of # possible ways to reach it by all # combinations of k leaps or less combo = [0] * (N + 1) # assuming leap 0 exist and assigning # its value to 1 for calculation combo[0] = 1 # loop to iterate over all # possible leaps upto k; for i in range(1, K + 1) : # in this loop we count all possible # leaps to reach the jth stair with # the help of ith leap or less for j in range(0, N + 1) : # if the leap is not more than the i-j if j >= i : # calculate the value and # store in combo[j] # to reuse it for next leap # calculation for the jth stair combo[j] += combo[j - i] # returns the no of possible number # of leaps to reach the top of # building of n stairs return combo[N] # Driver Code if __name__ == "__main__" : # N i the no of total stairs # K is the value of the greatest leap N, K = 29, 5 print(solve(N, K)) # This code is contributed by ANKITRAI1
C#
// C# program to reach N-th
// stair by taking a maximum
// of K leap
using System;
class GFG
{
static int solve(int N, int K)
{
// elements of combo[] stores
// the no. of possible ways
// to reach it by all combinations
// of k leaps or less
int[] combo;
combo = new int[50];
// assuming leap 0 exist
// and assigning its value
// to 1 for calculation
combo[0] = 1;
// loop to iterate over all
// possible leaps upto k;
for (int i = 1; i <= K; i++)
{
// in this loop we count all
// possible leaps to reach
// the jth stair with the
// help of ith leap or less
for (int j = 0; j <= N; j++)
{
// if the leap is not
// more than the i-j
if (j >= i)
{
// calculate the value and
// store in combo[j] to
// reuse it for next leap
// calculation for the
// jth stair
combo[j] += combo[j - i];
}
}
}
// returns the no of possible
// number of leaps to reach
// the top of building of
// n stairs
return combo[N];
}
// Driver Code
public static void Main()
{
// N i the no of total stairs
// K is the value of the
// greatest leap
int N = 29;
int K = 5;
Console.WriteLine(solve(N, K));
}
}
// This code is contributed
// by Akanksha Rai(Abby_akku)
PHP
<?php
error_reporting(0);
// PHP program to reach N-th
// stair by taking a maximum
// of K leap
function solve($N, $K)
{
// elements of combo[] stores
// the no of possible ways to
// reach it by all combinations
// of k leaps or less
$combo[$N + 1] = array();
// assuming leap 0 exist and
// assigning its value to 1
// for calculation
$combo[0] = 1;
// loop to iterate over all
// possible leaps upto k;
for ($i = 1; $i <= $K; $i++)
{
// in this loop we count
// all possible leaps to
// reach the jth stair with
// the help of ith leap or less
for ($j = 0; $j <= $N; $j++)
{
// if the leap is not
// more than the i-j
if ($j >= $i)
{
// calculate the value and
// store in combo[j]
// to reuse it for next leap
// calculation for the jth stair
$combo[$j] += $combo[$j - $i];
}
}
}
// returns the no of possible
// number of leaps to reach
// the top of building of n stairs
return $combo[$N];
}
// Driver Code
// N i the no of total stairs
// K is the value of the greatest leap
$N = 29;
$K = 5;
echo solve($N, $K);
// This code is contributed
// by Akanksha Rai(Abby_akku)
?>
Javascript
<script>
// Javascript program to reach N-th
// stair by taking a maximum
// of K leap
function solve(N, K)
{
// elements of combo[] stores
// the no. of possible ways
// to reach it by all combinations
// of k leaps or less
let combo = new Array(50);
combo.fill(0);
// assuming leap 0 exist
// and assigning its value
// to 1 for calculation
combo[0] = 1;
// loop to iterate over all
// possible leaps upto k;
for (let i = 1; i <= K; i++)
{
// in this loop we count all
// possible leaps to reach
// the jth stair with the
// help of ith leap or less
for (let j = 0; j <= N; j++)
{
// if the leap is not
// more than the i-j
if (j >= i)
{
// calculate the value and
// store in combo[j] to
// reuse it for next leap
// calculation for the
// jth stair
combo[j] += combo[j - i];
}
}
}
// returns the no of possible
// number of leaps to reach
// the top of building of
// n stairs
return combo[N];
}
// N i the no of total stairs
// K is the value of the
// greatest leap
let N = 29;
let K = 5;
document.write(solve(N, K));
// This code is contributed by decode2207.
</script>
Producción:
603
Complejidad temporal: O(N*K)
Espacio auxiliar: O(N)