Dadas N escaleras y una persona parada en la parte inferior quiere llegar a la cima. Podía subir cualquier cantidad de escalones desde la array dada arr[] de números enteros positivos. La tarea es encontrar la cuenta de todas las formas posibles de llegar a la cima.
Ejemplos:
Entrada: arr[] = {1, 3, 5}, N = 5
Salida: 5
(0 -> 1 -> 2 -> 3 -> 4 -> 5), (0 -> 1 -> 2 -> 5 ),
(0 -> 1 -> 4 -> 5), (0 -> 3 -> 4 -> 5)
y (0 -> 5) son las únicas formas posibles.
Entrada: arr[] = {1, 2, 3}, N = 10
Salida: 274
Enfoque ingenuo: utilizando la recursividad, encuentra todas las formas posibles y cuéntalas.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ implementation of the approach
#include <bits/stdc++.h>
using namespace std;
// Recursive function to return the
// total ways to reach the n'th stair
int countWays(int n, int arr[], int len)
{
// Base case
if (n == 0)
return 1;
// To store the number of ways
int no_ways = 0;
// Iterate each element of the given array
for (int i = 0; i < len; i++) {
// Here consider only the values of
// "n - arr[i]" >= 0 because negative values
// of n in the stair function are
// not defined
if (n - arr[i] >= 0) {
no_ways += countWays(n - arr[i], arr, len);
}
}
return no_ways;
}
// Driver code
int main()
{
int arr[] = { 1, 3, 5 };
int len = sizeof(arr) / sizeof(int);
int n = 5;
cout << countWays(n, arr, len);
return 0;
}
Java
// Java implementation of the approach
class GFG {
// Recursive function to return the
// total ways to reach the n'th stair
static int countWays(int n, int arr[], int len)
{
// Base case
if (n == 0)
return 1;
// To store the number of ways
int no_ways = 0;
// Iterate each element of the given array
for (int i = 0; i < len; i++) {
// Here consider only the values of
// "n - arr[i]" >= 0 because negative values
// of n in the stair function are
// not defined
if (n - arr[i] >= 0) {
no_ways += countWays(n - arr[i], arr, len);
}
}
return no_ways;
}
// Driver code
public static void main(String args[])
{
int arr[] = { 1, 3, 5 };
int len = arr.length;
;
int n = 5;
System.out.println(countWays(n, arr, len));
}
}
Python
# Python3 implementation of the approach # Recursive function to return the # total ways to reach the n'th stair def countWays(n, arr): # Base case if (n == 0): return 1 # To store the number of ways no_ways = 0 # Iterate each element of the given array for i in arr: # Here consider only the values of # "n - arr[i]" >= 0 because negative values # of n in the stair function are # not defined if (n - i >= 0): no_ways = no_ways + countWays(n - i, arr) return no_ways # Driver code arr = [1, 3, 5] n = 5 print(countWays(n, arr))
C#
// C# implementation of the approach
using System;
class GFG
{
// Recursive function to return the
// total ways to reach the n'th stair
static int countWays(int n, int []arr,
int len)
{
// Base case
if (n == 0)
return 1;
// To store the number of ways
int no_ways = 0;
// Iterate each element
// of the given array
for (int i = 0; i < len; i++)
{
// Here consider only the values of
// "n - arr[i]" >= 0 because negative values
// of n in the stair function are
// not defined
if (n - arr[i] >= 0)
{
no_ways += countWays(n - arr[i], arr, len);
}
}
return no_ways;
}
// Driver code
public static void Main()
{
int []arr = { 1, 3, 5 };
int len = arr.Length;
int n = 5;
Console.Write(countWays(n, arr, len));
}
}
// This code is contributed by Mohit Kumar
Javascript
<script>
// JavaScript implementation of the approach
// Recursive function to return the
// total ways to reach the n'th stair
function countWays(n, arr, len) {
// Base case
if (n == 0)
return 1;
// To store the number of ways
let no_ways = 0;
// Iterate each element of the given array
for (let i = 0; i < len; i++) {
// Here consider only the values of
// "n - arr[i]" >= 0 because negative values
// of n in the stair function are
// not defined
if (n - arr[i] >= 0) {
no_ways += countWays(n - arr[i], arr, len);
}
}
return no_ways;
}
// Driver code
let arr = [1, 3, 5];
let len = arr.length;
let n = 5;
document.write(countWays(n, arr, len));
</script>
Producción:
5
Enfoque eficiente: en este método, en lugar de utilizar un enfoque recursivo, opte por un enfoque basado en programación dinámica .
- Cree una array count[] de tamaño igual al número total de pasos + 1 con todos los elementos inicializados en 0 e inicialice el primer elemento, es decir, count[0] en 1.
- Inicialice una variable no_ways = 0 dentro del ciclo for y cada vez que comience desde 0 para las nuevas formas de subir las escaleras.
- Agregue count[i – x[j]] a no_ways solo si i – x[j] ≥ 0 .
- Finalmente, devuelva count[N], que es esencialmente el número de formas de subir el escalón N.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ implementation of the approach
#include <bits/stdc++.h>
using namespace std;
// Function to return the total number
// of ways to reach the n'th stair
int countWays(int n, int arr[], int len)
{
// To store the number of ways
// to reach the ith stair
int count[n + 1] = { 0 };
count[0] = 1;
// Base case
if (n == 0)
return 1;
// For every stair
for (int i = 1; i <= n; i++) {
// To store the count of ways
// till the current stair
int no_ways = 0;
// Every step from the array
for (int j = 0; j < len; j++) {
// Here consider only
// the values of "i - arr[j]" >= 0
// because negative values
// indicates reverse climbing
// of steps
if (i - arr[j] >= 0) {
no_ways += count[i - arr[j]];
}
count[i] = no_ways;
}
}
return count[n];
}
// Driver code
int main()
{
int arr[] = { 1, 3, 5 };
int len = sizeof(arr) / sizeof(int);
int n = 5;
cout << countWays(n, arr, len);
return 0;
}
Java
// java implementation of the approach
class GFG {
// Function to return the total number
// of ways to reach the n'th stair
static int countWays(int n, int arr[], int len)
{
// To store the number of ways
// to reach the ith stair
int count[] = new int[n + 1];
count[0] = 1;
// Base case
if (n == 0)
return 1;
// For every stair
for (int i = 1; i <= n; i++) {
// To store the count of ways
// till the current stair
int no_ways = 0;
// Every step from the array
for (int j = 0; j < len; j++) {
// Here consider only
// the values of "i - arr[j]" >= 0
// because negative values
// indicates reverse climbing
// of steps
if (i - arr[j] >= 0) {
no_ways += count[i - arr[j]];
}
count[i] = no_ways;
}
}
return count[n];
}
// Driver code
public static void main(String args[])
{
int arr[] = { 1, 3, 5 };
int len = arr.length;
int n = 5;
System.out.print(countWays(n, arr, len));
}
}
Python3
# Python3 implementation of the approach # Function to return the total number # of ways to reach the n'th stair def countWays(n, arr): # To store the number of ways # to reach the ith stair count = [0] * (n + 1) count[0] = 1 # Base case if (n == 0): return 1 # For every stair for i in range(1, n + 1): # To store the count of ways # till the current stair no_ways = 0 # Every step from the array for j in arr: # Here consider only # the values of "i - arr[j]" >= 0 # because negative values # indicates reverse climbing # of steps if (i - j >= 0): no_ways += count[i - j] count[i] = no_ways return count[n] # Driver code arr = [1, 3, 5] n = 5 print(countWays(n, arr))
C#
// C# implementation of the approach
using System;
class GFG
{
// Function to return the total number
// of ways to reach the n'th stair
static int countWays(int n, int []arr, int len)
{
// To store the number of ways
// to reach the ith stair
int []count = new int[n + 1];
count[0] = 1;
// Base case
if (n == 0)
return 1;
// For every stair
for (int i = 1; i <= n; i++)
{
// To store the count of ways
// till the current stair
int no_ways = 0;
// Every step from the array
for (int j = 0; j < len; j++)
{
// Here consider only
// the values of "i - arr[j]" >= 0
// because negative values
// indicates reverse climbing
// of steps
if (i - arr[j] >= 0)
{
no_ways += count[i - arr[j]];
}
count[i] = no_ways;
}
}
return count[n];
}
// Driver code
public static void Main()
{
int []arr = { 1, 3, 5 };
int len = arr.Length;
int n = 5;
Console.WriteLine(countWays(n, arr, len));
}
}
// This code is contributed by AnkitRai01
Javascript
<script>
// javascript implementation of the approach
// Function to return the total number
// of ways to reach the n'th stair
function countWays(n, arr, len)
{
// To store the number of ways
// to reach the ith stair
let count = new Array(n + 1);
count[0] = 1;
// Base case
if (n == 0)
return 1;
// For every stair
for (let i = 1; i <= n; i++) {
// To store the count of ways
// till the current stair
let no_ways = 0;
// Every step from the array
for (let j = 0; j < len; j++) {
// Here consider only
// the values of "i - arr[j]" >= 0
// because negative values
// indicates reverse climbing
// of steps
if (i - arr[j] >= 0) {
no_ways += count[i - arr[j]];
}
count[i] = no_ways;
}
}
return count[n];
}
let arr = [ 1, 3, 5 ];
let len = arr.length;
let n = 5;
document.write(countWays(n, arr, len));
// This code is contributed by divyeshrabadiya07.
</script>
Producción:
5
Complejidad de tiempo: O(N * len) donde N es el número de escaleras y len es la longitud de la array.
Publicación traducida automáticamente
Artículo escrito por imran_shaik y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA