Propiedad de superposición de subproblemas en programación dinámica | DP-1 – Part 1

 

La Programación Dinámica es un paradigma algorítmico que resuelve un problema complejo determinado al dividirlo en subproblemas usando la recursividad y almacenando los resultados de los subproblemas para evitar calcular los mismos resultados nuevamente. Las siguientes son las dos propiedades principales de un problema que sugiere que el problema dado se puede resolver mediante la programación dinámica.

En esta publicación, discutiremos la primera propiedad (Subproblemas superpuestos) en detalle. La segunda propiedad de la programación dinámica se analiza en la siguiente publicación, es decir , el Conjunto 2 .
1) Subproblemas superpuestos 
2) Subestructura óptima

C++

#include <iostream>
using namespace std;
 
/* a simple recursive program for Fibonacci numbers */
int fib(int n)
{
    if (n <= 1)
        return n;
  
    return fib(n - 1) + fib(n - 2);
}
 
int main() {
     
    cout << fib(7);
     
    return 0;
}
 
// This code is contributed by sanjoy_62.

C

/* a simple recursive program for Fibonacci numbers */
int fib(int n)
{
    if (n <= 1)
        return n;
 
    return fib(n - 1) + fib(n - 2);
}

Java

/*package whatever //do not write package name here */
/* a simple recursive program for Fibonacci numbers */
static int fib(int n)
{
    if (n <= 1)
        return n;
 
    return fib(n - 1) + fib(n - 2);
}
 
// This code is contributed by umadevi9616

Python

#  a simple recursive program for Fibonacci numbers
def fib(n):
    if n <= 1:
        return n
 
    return fib(n - 1) + fib(n - 2)

C#

/* a simple recursive program for Fibonacci numbers */
static int fib(int n)
{
    if (n <= 1)
        return n;
 
    return fib(n - 1) + fib(n - 2);
}
 
 
// This code contributed by umadevi9616

Javascript

<script>
/*package whatever //do not write package name here */
/* a simple recursive program for Fibonacci numbers */
function fib(n)
{
    if (n <= 1)
        return n;
 
    return fib(n - 1) + fib(n - 2);
}
 
// This code is contributed by gauravrajput1
</script>

C++

/* C++ program for Memoized version
for nth Fibonacci number */
#include <bits/stdc++.h>
using namespace std;
#define NIL -1
#define MAX 100
 
int lookup[MAX];
 
/* Function to initialize NIL
values in lookup table */
void _initialize()
{
    int i;
    for (i = 0; i < MAX; i++)
        lookup[i] = NIL;
}
 
/* function for nth Fibonacci number */
int fib(int n)
{
    if (lookup[n] == NIL) {
        if (n <= 1)
            lookup[n] = n;
        else
            lookup[n] = fib(n - 1) + fib(n - 2);
    }
 
    return lookup[n];
}
 
// Driver code
int main()
{
    int n = 40;
    _initialize();
    cout << "Fibonacci number is " << fib(n);
    return 0;
}
 
// This is code is contributed by rathbhupendra

C

/* C program for Memoized version for nth Fibonacci number
 */
#include <stdio.h>
#define NIL -1
#define MAX 100
 
int lookup[MAX];
 
/* Function to initialize NIL values in lookup table */
void _initialize()
{
    int i;
    for (i = 0; i < MAX; i++)
        lookup[i] = NIL;
}
 
/* function for nth Fibonacci number */
int fib(int n)
{
    if (lookup[n] == NIL) {
        if (n <= 1)
            lookup[n] = n;
        else
            lookup[n] = fib(n - 1) + fib(n - 2);
    }
 
    return lookup[n];
}
 
int main()
{
    int n = 40;
    _initialize();
    printf("Fibonacci number is %d ", fib(n));
    return 0;
}

Java

/* Java program for Memoized version */
public class Fibonacci {
    final int MAX = 100;
    final int NIL = -1;
 
    int lookup[] = new int[MAX];
 
    /* Function to initialize NIL values in lookup table */
    void _initialize()
    {
        for (int i = 0; i < MAX; i++)
            lookup[i] = NIL;
    }
 
    /* function for nth Fibonacci number */
    int fib(int n)
    {
        if (lookup[n] == NIL) {
            if (n <= 1)
                lookup[n] = n;
            else
                lookup[n] = fib(n - 1) + fib(n - 2);
        }
        return lookup[n];
    }
 
    public static void main(String[] args)
    {
        Fibonacci f = new Fibonacci();
        int n = 40;
        f._initialize();
        System.out.println("Fibonacci number is"
                           + " " + f.fib(n));
    }
}
// This Code is Contributed by Saket Kumar

Python

# a program for Memoized version of nth Fibonacci number
 
# function to calculate nth Fibonacci number
 
 
def fib(n, lookup):
 
    # base case
    if n <= 1:
        lookup[n] = n
 
    # if the value is not calculated previously then calculate it
    if lookup[n] is None:
        lookup[n] = fib(n-1, lookup) + fib(n-2, lookup)
 
    # return the value corresponding to that value of n
    return lookup[n]
# end of function
 
# Driver program to test the above function
 
 
def main():
    n = 34
    # Declaration of lookup table
    # Handles till n = 100
    lookup = [None] * 101
    print "Fibonacci Number is ", fib(n, lookup)
 
 
if __name__ == "__main__":
    main()
 
# This code is contributed by Nikhil Kumar Singh(nickzuck_007)

C#

// C# program for Memoized versionof nth Fibonacci number
using System;
 
class GFG {
 
    static int MAX = 100;
    static int NIL = -1;
    static int[] lookup = new int[MAX];
 
    /* Function to initialize NIL
    values in lookup table */
    static void initialize()
    {
        for (int i = 0; i < MAX; i++)
            lookup[i] = NIL;
    }
 
    /* function for nth Fibonacci number */
    static int fib(int n)
    {
        if (lookup[n] == NIL) {
            if (n <= 1)
                lookup[n] = n;
            else
                lookup[n] = fib(n - 1) + fib(n - 2);
        }
        return lookup[n];
    }
 
    // Driver code
    public static void Main()
    {
 
        int n = 40;
        initialize();
        Console.Write("Fibonacci number is"
                      + " " + fib(n));
    }
}
 
// This Code is Contributed by Sam007

Javascript

<script>
 
let  MAX = 100;
let NIL = -1;
 
let lookup = new Array(MAX);
 
function  _initialize()
{
    for (let i = 0; i < MAX; i++)
        lookup[i] = NIL;
}
 
function fib(n)
{
    if (lookup[n] == NIL)
    {
      if (n <= 1)
          lookup[n] = n;
      else
          lookup[n] = fib(n-1) + fib(n-2);
    }
    return lookup[n];
}
 
 
let n = 40;
_initialize();
document.write("Fibonacci number is" + " " + fib(n)+"<br>");
 
// This code is contributed by avanitrachhadiya2155
</script>

C

/* C program for Tabulated version */
#include <stdio.h>
int fib(int n)
{
    int f[n + 1];
    int i;
    f[0] = 0;
    f[1] = 1;
    for (i = 2; i <= n; i++)
        f[i] = f[i - 1] + f[i - 2];
 
    return f[n];
}
 
int main()
{
    int n = 9;
    printf("Fibonacci number is %d ", fib(n));
    return 0;
}

Java

/* Java program for Tabulated version */
public class Fibonacci {
    int fib(int n)
    {
        int f[] = new int[n + 1];
        f[0] = 0;
        f[1] = 1;
        for (int i = 2; i <= n; i++)
            f[i] = f[i - 1] + f[i - 2];
        return f[n];
    }
 
    public static void main(String[] args)
    {
        Fibonacci f = new Fibonacci();
        int n = 9;
        System.out.println("Fibonacci number is"
                           + " " + f.fib(n));
    }
}
// This Code is Contributed by Saket Kumar

Python

# Python program Tabulated (bottom up) version
def fib(n):
 
    # array declaration
    f = [0] * (n + 1)
 
    # base case assignment
    f[1] = 1
 
    # calculating the fibonacci and storing the values
    for i in xrange(2, n + 1):
        f[i] = f[i - 1] + f[i - 2]
    return f[n]
 
# Driver program to test the above function
 
 
def main():
    n = 9
    print "Fibonacci number is ", fib(n)
 
 
if __name__ == "__main__":
    main()
 
# This code is contributed by Nikhil Kumar Singh (nickzuck_007)

C#

// C# program for Tabulated version
using System;
 
class GFG {
    static int fib(int n)
    {
        int[] f = new int[n + 1];
        f[0] = 0;
        f[1] = 1;
        for (int i = 2; i <= n; i++)
            f[i] = f[i - 1] + f[i - 2];
        return f[n];
    }
 
    public static void Main()
    {
 
        int n = 9;
        Console.Write("Fibonacci number is"
                      + " " + fib(n));
    }
}
 
// This Code is Contributed by Sam007

Javascript

<script>
 
// Javascript program for Tabulated version
function fib(n)
{
    var f = new Array(n + 1);
    var i;
     
    f[0] = 0;
    f[1] = 1;
    for(i = 2; i <= n; i++)
        f[i] = f[i - 1] + f[i - 2];
     
    return f[n];
}
 
// Driver code
var n = 9;
document.write("Fibonacci number is  " + fib(n));
 
// This code is contributed by akshitsaxenaa09
 
</script>

PHP

<?php
// PHP program for Tabulated version
 
function fib($n)
{
    $f[$n + 1]=0;
    $i;
    $f[0] = 0;
    $f[1] = 1;
    for ($i = 2; $i <= $n; $i++)
        $f[$i] = $f[$i - 1] +
                 $f[$i - 2];
     
    return $f[$n];
}
 
// Driver Code
$n = 9;
echo("Fibonacci number is ");
echo(fib($n));
 
// This code is contributed by nitin mittal.
?>

C++

/* C++ program for Tabulated version */
 
#include <iostream>
using namespace std;
 
int fib(int n)
{
    int f[n + 1];
    int i;
    f[0] = 0;
    f[1] = 1;
    for (i = 2; i <= n; i++)
        f[i] = f[i - 1] + f[i - 2];
 
    return f[n];
}
 
int main()
{
    int n = 9;
    printf("Fibonacci number is %d ", fib(n));
    return 0;
}

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

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *