Dada una distancia ‘dist’, cuente el número total de formas de cubrir la distancia con 1, 2 y 3 pasos.
Ejemplos:
Input: n = 3 Output: 4 Explanation: Below are the four ways 1 step + 1 step + 1 step 1 step + 2 step 2 step + 1 step 3 step Input: n = 4 Output: 7 Explanation: Below are the four ways 1 step + 1 step + 1 step + 1 step 1 step + 2 step + 1 step 2 step + 1 step + 1 step 1 step + 1 step + 2 step 2 step + 2 step 3 step + 1 step 1 step + 3 step
solución recursiva
- Aproximación: Hay n escaleras, y una persona puede dar el siguiente paso, saltarse una posición o saltarse dos posiciones. Entonces hay n posiciones. La idea es pararse en la i-ésima posición en la que la persona puede moverse en la posición i+1, i+2, i+3. Por lo tanto, se puede formar una función recursiva donde, en el índice actual i, la función se llama recursivamente para las posiciones i+1, i+2 e i+3.
Hay otra forma de formar la función recursiva. Para alcanzar la posición i, una persona tiene que saltar desde la posición i-1, i-2 o i-3 donde i es la posición inicial.
- Algoritmo:
- Cree una función recursiva ( count(int n) ) que tome solo un parámetro.
- Revisa los casos base. Si el valor de n es menor que 0, devuelva 0, y si el valor de n es igual a cero, devuelva 1, ya que es la posición inicial.
- Llame a la función recursivamente con valores n-1, n-2 y n-3 y sume los valores que se devuelven, es decir, sum = count(n-1) + count(n-2) + count(n-3) .
- Devuelve el valor de la suma .
- Implementación:
C++
// A naive recursive C++ program to count number of ways to cover
// a distance with 1, 2 and 3 steps
#include<iostream>
using namespace std;
// Returns count of ways to cover 'dist'
int printCountRec(int dist)
{
// Base cases
if (dist<0) return 0;
if (dist==0) return 1;
// Recur for all previous 3 and add the results
return printCountRec(dist-1) +
printCountRec(dist-2) +
printCountRec(dist-3);
}
// driver program
int main()
{
int dist = 4;
cout << printCountRec(dist);
return 0;
}
Java
// A naive recursive Java program to count number
// of ways to cover a distance with 1, 2 and 3 steps
import java.io.*;
class GFG
{
// Function returns count of ways to cover 'dist'
static int printCountRec(int dist)
{
// Base cases
if (dist<0)
return 0;
if (dist==0)
return 1;
// Recur for all previous 3 and add the results
return printCountRec(dist-1) +
printCountRec(dist-2) +
printCountRec(dist-3);
}
// driver program
public static void main (String[] args)
{
int dist = 4;
System.out.println(printCountRec(dist));
}
}
// This code is contributed by Pramod Kumar
Python3
# A naive recursive Python3 program # to count number of ways to cover # a distance with 1, 2 and 3 steps # Returns count of ways to # cover 'dist' def printCountRec(dist): # Base cases if dist < 0: return 0 if dist == 0: return 1 # Recur for all previous 3 and # add the results return (printCountRec(dist-1) + printCountRec(dist-2) + printCountRec(dist-3)) # Driver code dist = 4 print(printCountRec(dist)) # This code is contributed by Anant Agarwal.
C#
// A naive recursive C# program to
// count number of ways to cover a
// distance with 1, 2 and 3 steps
using System;
class GFG {
// Function returns count of
// ways to cover 'dist'
static int printCountRec(int dist)
{
// Base cases
if (dist < 0)
return 0;
if (dist == 0)
return 1;
// Recur for all previous 3
// and add the results
return printCountRec(dist - 1) +
printCountRec(dist - 2) +
printCountRec(dist - 3);
}
// Driver Code
public static void Main ()
{
int dist = 4;
Console.WriteLine(printCountRec(dist));
}
}
// This code is contributed by Sam007.
PHP
<?php
// A naive recursive PHP program to
// count number of ways to cover
// a distance with 1, 2 and 3 steps
// Returns count of ways to cover 'dist'
function printCountRec( $dist)
{
// Base cases
if ($dist<0) return 0;
if ($dist==0) return 1;
// Recur for all previous 3
// and add the results
return printCountRec($dist - 1) +
printCountRec($dist - 2) +
printCountRec($dist - 3);
}
// Driver Code
$dist = 4;
echo printCountRec($dist);
// This code is contributed by anuj_67.
?>
Javascript
<script>
// A naive recursive javascript program to count number of ways to cover
// a distance with 1, 2 and 3 steps
// Returns count of ways to cover 'dist'
function printCountRec(dist)
{
// Base cases
if (dist<0) return 0;
if (dist==0) return 1;
// Recur for all previous 3 and add the results
return printCountRec(dist-1) +
printCountRec(dist-2) +
printCountRec(dist-3);
}
// driver program
var dist = 4;
document.write(printCountRec(dist));
</script>
Producción:
7
- Análisis de Complejidad:
- Complejidad temporal: O(3 n ).
La complejidad temporal de la solución anterior es exponencial, un límite superior cercano es O(3 n ). De cada estado 3, se llama una función recursiva. Entonces el límite superior para n estados es O(3 n ). - Complejidad espacial: O(1).
No se requiere espacio adicional.
- Complejidad temporal: O(3 n ).
Solución eficiente
- Planteamiento: La idea es similar, pero se puede observar que hay n estados pero la función recursiva se llama 3^n veces. Eso significa que algunos estados son llamados repetidamente. Así que la idea es almacenar el valor de los estados. Esto se puede hacer de dos formas.
- La primera forma es mantener intacta la estructura recursiva y simplemente almacenar el valor en un HashMap y cada vez que se llame a la función, devolver el valor almacenado sin computar (enfoque de arriba hacia abajo).
- La segunda forma es tomar un espacio adicional de tamaño n y comenzar a calcular los valores de los estados de 1, 2 .. a n, es decir, calcular los valores de i, i+1, i+2 y luego usarlos para calcular el valor de i +3 (Enfoque de abajo hacia arriba).
- Subproblemas superpuestos en programación dinámica.
- Propiedad de subestructura óptima en Programación Dinámica.
- Problemas de programación dinámica (DP)
- Algoritmo:
- Cree una array de tamaño n + 1 e inicialice las primeras 3 variables con 1, 1, 2. Los casos base.
- Ejecute un ciclo de 3 a n.
- Para cada índice i, calcule el valor de la i-ésima posición como dp[i] = dp[i-1] + dp[i-2] + dp[i-3] .
- Imprime el valor de dp[n], como el Conteo del número de formas de cubrir una distancia.
- Implementación:
C++
// A Dynamic Programming based C++ program to count number of ways
// to cover a distance with 1, 2 and 3 steps
#include<iostream>
using namespace std;
int printCountDP(int dist)
{
int count[dist+1];
// Initialize base values. There is one way to cover 0 and 1
// distances and two ways to cover 2 distance
count[0] = 1;
if(dist >= 1)
count[1] = 1;
if(dist >= 2)
count[2] = 2;
// Fill the count array in bottom up manner
for (int i=3; i<=dist; i++)
count[i] = count[i-1] + count[i-2] + count[i-3];
return count[dist];
}
// driver program
int main()
{
int dist = 4;
cout << printCountDP(dist);
return 0;
}
Java
// A Dynamic Programming based Java program
// to count number of ways to cover a distance
// with 1, 2 and 3 steps
import java.io.*;
class GFG
{
// Function returns count of ways to cover 'dist'
static int printCountDP(int dist)
{
int[] count = new int[dist+1];
// Initialize base values. There is one way to
// cover 0 and 1 distances and two ways to
// cover 2 distance
count[0] = 1;
if(dist >= 1)
count[1] = 1;
if(dist >= 2)
count[2] = 2;
// Fill the count array in bottom up manner
for (int i=3; i<=dist; i++)
count[i] = count[i-1] + count[i-2] + count[i-3];
return count[dist];
}
// driver program
public static void main (String[] args)
{
int dist = 4;
System.out.println(printCountDP(dist));
}
}
// This code is contributed by Pramod Kumar
Python3
# A Dynamic Programming based on Python3 # program to count number of ways to # cover a distance with 1, 2 and 3 steps def printCountDP(dist): count = [0] * (dist + 1) # Initialize base values. There is # one way to cover 0 and 1 distances # and two ways to cover 2 distance count[0] = 1 if dist >= 1 : count[1] = 1 if dist >= 2 : count[2] = 2 # Fill the count array in bottom # up manner for i in range(3, dist + 1): count[i] = (count[i-1] + count[i-2] + count[i-3]) return count[dist]; # driver program dist = 4; print( printCountDP(dist)) # This code is contributed by Sam007.
C#
// A Dynamic Programming based C# program
// to count number of ways to cover a distance
// with 1, 2 and 3 steps
using System;
class GFG {
// Function returns count of ways
// to cover 'dist'
static int printCountDP(int dist)
{
int[] count = new int[dist + 1];
// Initialize base values. There is one
// way to cover 0 and 1 distances
// and two ways to cover 2 distance
count[0] = 1;
count[1] = 1;
count[2] = 2;
// Fill the count array
// in bottom up manner
for (int i = 3; i <= dist; i++)
count[i] = count[i - 1] +
count[i - 2] +
count[i - 3];
return count[dist];
}
// Driver Code
public static void Main ()
{
int dist = 4;
Console.WriteLine(printCountDP(dist));
}
}
// This code is contributed by Sam007.
PHP
<?php
// A Dynamic Programming based PHP program
// to count number of ways to cover a
// distance with 1, 2 and 3 steps
function printCountDP( $dist)
{
$count = array();
// Initialize base values. There is
// one way to cover 0 and 1 distances
// and two ways to cover 2 distance
$count[0] = 1; $count[1] = 1;
$count[2] = 2;
// Fill the count array
// in bottom up manner
for ( $i = 3; $i <= $dist; $i++)
$count[$i] = $count[$i - 1] +
$count[$i - 2] +
$count[$i - 3];
return $count[$dist];
}
// Driver Code
$dist = 4;
echo printCountDP($dist);
// This code is contributed by anuj_67.
?>
Javascript
<script>
// A Dynamic Programming based Javascript program
// to count number of ways to cover a distance
// with 1, 2 and 3 steps
// Function returns count of ways
// to cover 'dist'
function printCountDP(dist)
{
let count = new Array(dist + 1);
// Initialize base values. There is one
// way to cover 0 and 1 distances
// and two ways to cover 2 distance
count[0] = 1;
if (dist >= 1)
count[1] = 1;
if (dist >= 2)
count[2] = 2;
// Fill the count array
// in bottom up manner
for(let i = 3; i <= dist; i++)
count[i] = count[i - 1] +
count[i - 2] +
count[i - 3];
return count[dist];
}
// Driver code
let dist = 4;
document.write(printCountDP(dist));
// This code is contributed by divyeshrabadiya07
</script>
Producción :
7
- Análisis de Complejidad:
- Complejidad temporal: O(n).
Solo se necesita un recorrido de la array. Entonces la complejidad del tiempo es O(n) - Complejidad espacial: O(n).
Para almacenar los valores en un DP O(n) se necesita espacio extra.
- Complejidad temporal: O(n).
Solución más óptima
Enfoque: en lugar de usar una array de tamaño n+1, podemos usar una array de tamaño 3 porque para calcular el número de formas para un paso en particular solo necesitamos los últimos 3 pasos sin número de formas.
Algoritmo:
- Cree una array de tamaño 3 e inicialice los valores para el paso 0,1,2 como 1,1,2 (casos base).
- Ejecute un ciclo de 3 a n(dist).
- Para cada índice, calcule el valor como vías[i%3] = vías[(i-1)%3] + vías[(i-2)%3] + vías[(i-3)%3] y almacene su valor en i%3 índice de formas de array. Si estamos calculando el valor para el índice 3, el valor calculado irá al índice 0 porque para índices más grandes (4, 5, 6…..) no necesitamos el valor del índice 0.
- Devuelve el valor de vías[n%3].
C++
// A Dynamic Programming based C++ program to count number of ways
#include<iostream>
using namespace std;
int printCountDP(int dist)
{
//Create the array of size 3.
int ways[3] , n = dist;
//Initialize the bases cases
ways[0] = 1;
ways[1] = 1;
ways[2] = 2;
//Run a loop from 3 to n
//Bottom up approach to fill the array
for(int i=3 ;i<=n ;i++)
ways[i%3] = ways[(i-1)%3] + ways[(i-2)%3] + ways[(i-3)%3];
return ways[n%3];
}
// driver program
int main()
{
int dist = 4;
cout << printCountDP(dist);
return 0;
}
Java
// A Dynamic Programming based Java program to count number of ways
import java.util.*;
class GFG {
static int printCountDP(int dist)
{
// Create the array of size 3.
int []ways = new int[3];
int n = dist;
// Initialize the bases cases
ways[0] = 1;
ways[1] = 1;
ways[2] = 2;
// Run a loop from 3 to n
// Bottom up approach to fill the array
for(int i=3 ;i<=n ;i++)
ways[i%3] = ways[(i-1)%3] + ways[(i-2)%3] + ways[(i-3)%3];
return ways[n%3];
}
// driver program
public static void main(String arg[])
{
int dist = 4;
System.out.print(printCountDP(dist));
}
}
// this code is contributed by shivanisinghss2110
Python3
# A Dynamic Programming based C++ program to count number of ways def prCountDP( dist): # Create the array of size 3. ways = [0]*3 n = dist # Initialize the bases cases ways[0] = 1 ways[1] = 1 ways[2] = 2 # Run a loop from 3 to n # Bottom up approach to fill the array for i in range(3, n + 1): ways[i % 3] = ways[(i - 1) % 3] + ways[(i - 2) % 3] + ways[(i - 3) % 3] return ways[n % 3] # driver program dist = 4 print(prCountDP(dist)) # This code is contributed by shivanisinghss2110
C#
// A Dynamic Programming based C#
// program to count number of ways
using System;
class GFG{
static int printCountDP(int dist)
{
// Create the array of size 3.
int []ways = new int[3];
int n = dist;
// Initialize the bases cases
ways[0] = 1;
ways[1] = 1;
ways[2] = 2;
// Run a loop from 3 to n
// Bottom up approach to fill the array
for(int i = 3; i <= n; i++)
ways[i % 3] = ways[(i - 1) % 3] +
ways[(i - 2) % 3] +
ways[(i - 3) % 3];
return ways[n % 3];
}
// Driver code
public static void Main(String []arg)
{
int dist = 4;
Console.Write(printCountDP(dist));
}
}
// This code is contributed by shivanisinghss2110
Javascript
<script>
// A Dynamic Programming based javascript program to count number of ways
function printCountDP( dist)
{
//Create the array of size 3.
var ways= [] , n = dist;
ways.length = 3 ;
//Initialize the bases cases
ways[0] = 1;
ways[1] = 1;
ways[2] = 2;
//Run a loop from 3 to n
//Bottom up approach to fill the array
for(var i=3 ;i<=n ;i++)
ways[i%3] = ways[(i-1)%3] + ways[(i-2)%3] + ways[(i-3)%3];
return ways[n%3];
}
// driver code
var dist = 4;
document.write(printCountDP(dist));
</script>
Producción :
7
Complejidad de tiempo : O(n)
Complejidad espacial : O(1)
Este artículo es una contribución de Vignesh Venkatesan. Escriba comentarios si encuentra algo incorrecto o si desea compartir más información sobre el tema tratado anteriormente.
Publicación traducida automáticamente
Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA