Suma máxima de caminos en un triángulo.

Hemos dado números en forma de triángulo, comenzando en la parte superior del triángulo y moviéndose a los números adyacentes en la fila de abajo, encuentre el total máximo de arriba hacia abajo. 
Ejemplos: 

Input : 
   3
  7 4
 2 4 6
8 5 9 3
Output : 23
Explanation : 3 + 7 + 4 + 9 = 23 

Input :
   8
 -4 4
 2 2 6
1 1 1 1
Output : 19
Explanation : 8 + 4 + 6 + 1 = 19

Método 1 : podemos utilizar la fuerza bruta comprobando todos los caminos posibles, pero eso lleva mucho tiempo, por lo que debemos tratar de resolver este problema con la ayuda de la programación dinámica que reduce la complejidad del tiempo. 

Implementación del enfoque recursivo:

C++

// C++ program for
// Recursive implementation of
// Max sum problem in a triangle
#include<bits/stdc++.h>
using namespace std;
#define N 3
 
//  Function for finding maximum sum
int maxPathSum(int tri[][N], int i, int j, int row, int col){
     if(j == col ){
         return 0;
     }
   
     if(i == row-1 ){
         return tri[i][j] ;
     }
   
     return tri[i][j] + max(maxPathSum(tri, i+1, j, row, col),
                            maxPathSum(tri, i+1, j+1, row, col)) ;
}
 
/* Driver program to test above functions */
int main()
{
   int tri[N][N] = {  {1, 0, 0},
                      {4, 8, 0},
                      {1, 5, 3} };
   cout << maxPathSum(tri, 0, 0, 3, 3);
   return 0;
}

Java

// Java program for
// Recursive implementation of
// Max sum problem in a triangle
import java.io.*;
 
class GFG {
    static int N = 3;
 
    //  Function for finding maximum sum
    public static int maxPathSum(int tri[][], int i, int j,
                                 int row, int col)
    {
        if (j == col) {
            return 0;
        }
 
        if (i == row - 1) {
            return tri[i][j];
        }
 
        return tri[i][j]
            + Math.max(
                maxPathSum(tri, i + 1, j, row, col),
                maxPathSum(tri, i + 1, j + 1, row, col));
    }
 
    /* Driver program to test above functions */
    public static void main(String[] args)
    {
        int tri[][]
            = { { 1, 0, 0 }, { 4, 8, 0 }, { 1, 5, 3 } };
        System.out.print(maxPathSum(tri, 0, 0, 3, 3));
    }
}
 
// This code is contributed by Rohit Pradhan

Python3

# Python program for
# Recursive implementation of
# Max sum problem in a triangle
N = 3
 
#  Function for finding maximum sum
def maxPathSum(tri, i, j, row, col):
     if(j == col ):
         return 0
   
     if(i == row-1 ):
         return tri[i][j]
   
     return tri[i][j] + max(maxPathSum(tri, i+1, j, row, col),
                            maxPathSum(tri, i+1, j+1, row, col))
 
# Driver program to test above functions
tri = [  [1, 0, 0],[4, 8, 0],[1, 5, 3] ]
print(maxPathSum(tri, 0, 0, 3, 3))
 
# This code is contributed by shinjanpatra

Javascript

<script>
 
// JavaScript program for
// Recursive implementation of
// Max sum problem in a triangle
 
const N = 3
 
//  Function for finding maximum sum
function maxPathSum(tri, i, j, row, col){
     if(j == col ){
         return 0;
     }
   
     if(i == row-1 ){
         return tri[i][j] ;
     }
   
     return tri[i][j] + Math.max(maxPathSum(tri, i+1, j, row, col),
                            maxPathSum(tri, i+1, j+1, row, col)) ;
}
 
/* Driver program to test above functions */
let tri = [  [1, 0, 0],[4, 8, 0],[1, 5, 3] ];
document.write(maxPathSum(tri, 0, 0, 3, 3));
 
// This code is contributed by shinjanpatra
 
</script>
Producción

14

Análisis de Complejidad:

  • Complejidad del tiempo: O(2 N*N )
  • Complejidad espacial:   O(N)

Si debemos desplazar a la izquierda cada elemento y poner 0 en cada posición vacía para convertirlo en una array regular, entonces nuestro problema parece una ruta de costo mínimo.  
Entonces, después de convertir nuestros elementos triangulares de entrada en una array regular, debemos aplicar el concepto de programación dinámica para encontrar la suma máxima de rutas. 

Método 2: DP de arriba hacia abajo
Dado que hay subproblemas superpuestos, podemos evitar el trabajo repetido realizado en el método 1 almacenando la ruta de costo mínimo calculada hasta ahora usando el enfoque de arriba hacia abajo

C++

// C++ program for Dynamic
// Programming implementation (Top-Down) of
// Max sum problem in a triangle
#include<bits/stdc++.h>
using namespace std;
#define N 3
 
//  Function for finding maximum sum
int maxPathSum(int tri[][N], int i, int j, int row, int col, vector<vector<int>> &dp){
     if(j == col ){
         return 0;
     }
   
     if(i == row-1 ){
         return tri[i][j] ;
     }
   
     if(dp[i][j] != -1){
         return dp[i][j] ;
     }
   
     return dp[i][j] = tri[i][j] + max(maxPathSum(tri, i+1, j, row, col, dp),
                                   maxPathSum(tri, i+1, j+1, row, col, dp)) ;
}
 
/* Driver program to test above functions */
int main()
{
   int tri[N][N] = {  {1, 0, 0},
                      {4, 8, 0},
                      {1, 5, 3} };
   vector<vector<int>> dp(N, vector<int>(N, -1) ) ;
   cout << maxPathSum(tri, 0, 0, N, N, dp);
   return 0;
}

Python3

# C++ program for Dynamic
# Programming implementation (Top-Down) of
# Max sum problem in a triangle
N = 3
 
#  Function for finding maximum sum
def maxPathSum(tri, i, j, row, col, dp):
     if(j == col):
         return 0
   
     if(i == row-1):
         return tri[i][j]
   
     if(dp[i][j] != -1):
         return -1
   
     dp[i][j] = tri[i][j] + max(maxPathSum(tri, i+1, j, row, col, dp),
                                   maxPathSum(tri, i+1, j+1, row, col, dp))
     return dp[i][j]
 
# Driver program to test above functions
tri = [ [1, 0, 0],
        [4, 8, 0],
        [1, 5, 3] ]
dp = [[-1 for i in range(N)]for j in range(N)]
print(maxPathSum(tri, 0, 0, N, N, dp))
 
 
# This code is contributed by shinjanpatra

Javascript

<script>
 
b// JavaScript program for Dynamic
// Programming implementation (Top-Down) of
// Max sum problem in a triangle
const N = 3
 
//  Function for finding maximum sum
function maxPathSum(tri, i, j, row, col, dp){
     if(j == col)
         return 0
   
     if(i == row-1)
         return tri[i][j]
   
     if(dp[i][j] != -1)
         return -1
   
     dp[i][j] = tri[i][j] + Math.max(maxPathSum(tri, i+1, j, row, col, dp),
                                   maxPathSum(tri, i+1, j+1, row, col, dp))
     return dp[i][j]
}
 
// Driver program to test above functions
let tri = [ [1, 0, 0],
        [4, 8, 0],
        [1, 5, 3] ]
let dp = new Array(N).fill(-1).map(()=>new Array(N).fill(-1))
document.write(maxPathSum(tri, 0, 0, N, N, dp),"</br>")
 
// This code is contributed by shinjanpatra
 
</script>
Producción

14

Análisis de Complejidad:

  • Complejidad de tiempo:  O(m*n) donde m = número de filas y n = número de columnas
  • Complejidad espacial: O(n 2 )

Método 3: DP (de abajo a arriba)
Dado que hay subproblemas superpuestos, podemos evitar el trabajo repetido realizado en el método 1 almacenando la ruta de costo mínimo calculada hasta ahora usando el enfoque de abajo hacia arriba, reduciendo así el espacio de pila

C++

// C++ program for Dynamic
// Programming implementation of
// Max sum problem in a triangle
#include<bits/stdc++.h>
using namespace std;
#define N 3
 
//  Function for finding maximum sum
int maxPathSum(int tri[][N], int n, vector<vector<int>> &dp)
{
     // loop for bottom-up calculation
     for(int j = 0; j < n; j++ ){
            dp[n-1][j] = tri[n-1][j] ;
        }
         
        for(int i = n-2; i >= 0; i--){
            for(int j = i; j >= 0; j-- ){
                dp[i][j] = tri[i][j] + max(dp[i+1][j] , dp[i+1][j+1]) ;
            }
        }
         
        return dp[0][0] ;
      
}
 
/* Driver program to test above functions */
int main()
{
   int tri[N][N] = {  {1, 0, 0},
                      {4, 8, 0},
                      {1, 5, 3} };
   vector<vector<int>> dp(N, vector<int>(N, -1) ) ;
   cout << maxPathSum(tri, N, dp);
   return 0;
}
Producción

14

Análisis de Complejidad:

  • Complejidad de tiempo: O(m*n) donde m = número de filas y n = número de columnas
  • Complejidad espacial: O(n 2 )

Método 4: Optimización del espacio (sin cambiar la array de entrada)
No necesitamos una array 2d, solo necesitamos una array 1d que almacene el mínimo de la siguiente columna inmediata y, por lo tanto, podemos reducir el espacio

C++

// C++ program for Dynamic
// Programming implementation of
// Max sum problem in a triangle
#include<bits/stdc++.h>
using namespace std;
#define N 3
 
//  Function for finding maximum sum
int maxPathSum(int tri[][N], int n, vector<vector<int>> &dp)
{
        vector<int> front(n, -1) , curr(n, -1) ;
        
        for(int j = 0; j < n; j++ ){
            front[j] = tri[n-1][j] ;
        }
         
        for(int i = n-2; i >= 0; i--){
            for(int j = i; j >= 0; j-- ){
                curr[j] = tri[i][j] + max(front[j] , front[j+1]) ;
            }
            front = curr ;
        }
         
        return front[0] ;
      
}
 
/* Driver program to test above functions */
int main()
{
   int tri[N][N] = {  {1, 0, 0},
                      {4, 8, 0},
                      {1, 5, 3} };
   vector<vector<int>> dp(N, vector<int>(N, -1) ) ;
   cout << maxPathSum(tri, N, dp);
   return 0;
}
Producción

14

Análisis de Complejidad:

  • Complejidad de tiempo: O(m*n) donde m = número de filas y n = número de columnas
  • Complejidad espacial: O(n)

Método 5: Optimización del espacio (array de entrada cambiante)
Aplicando DP de forma ascendente, deberíamos resolver nuestro problema como: 
Ejemplo: 

   3
  7 4
 2 4 6
8 5 9 3

Step 1 :
3 0 0 0
7 4 0 0
2 4 6 0
8 5 9 3

Step 2 :
3  0  0  0
7  4  0  0
10 13 15 0

Step 3 :
3  0  0  0
20 19 0  0

Step 4:
23 0 0 0

output : 23

C++

// C++ program for Dynamic
// Programming implementation of
// Max sum problem in a triangle
#include<bits/stdc++.h>
using namespace std;
#define N 3
 
//  Function for finding maximum sum
int maxPathSum(int tri[][N], int m, int n)
{
     // loop for bottom-up calculation
     for (int i=m-1; i>=0; i--)
     {
        for (int j=0; j<=i; j++)
        {
            // for each element, check both
            // elements just below the number
            // and below right to the number
            // add the maximum of them to it
            if (tri[i+1][j] > tri[i+1][j+1])
                tri[i][j] += tri[i+1][j];
            else
                tri[i][j] += tri[i+1][j+1];
        }
     }
 
     // return the top element
     // which stores the maximum sum
     return tri[0][0];
}
 
/* Driver program to test above functions */
int main()
{
   int tri[N][N] = {  {1, 0, 0},
                      {4, 8, 0},
                      {1, 5, 3} };
   cout << maxPathSum(tri, 2, 2);
   return 0;
}

Java

// Java Program for Dynamic
// Programming implementation of
// Max sum problem in a triangle
import java.io.*;
 
class GFG {
         
    static int N = 3;
     
    // Function for finding maximum sum
    static int maxPathSum(int tri[][], int m, int n)
    {
        // loop for bottom-up calculation
        for (int i = m - 1; i >= 0; i--)
        {
            for (int j = 0; j <= i; j++)
            {
                // for each element, check both
                // elements just below the number
                // and below right to the number
                // add the maximum of them to it
                if (tri[i + 1][j] > tri[i + 1][j + 1])
                    tri[i][j] += tri[i + 1][j];
                else
                    tri[i][j] += tri[i + 1][j + 1];
            }
        }
     
        // return the top element
        // which stores the maximum sum
        return tri[0][0];
    }
     
    /* Driver program to test above functions */
    public static void main (String[] args)
    {
        int tri[][] = { {1, 0, 0},
                        {4, 8, 0},
                        {1, 5, 3} };
        System.out.println ( maxPathSum(tri, 2, 2));
    }
}
 
// This code is contributed by vt_m

Python3

# Python program for
# Dynamic Programming
# implementation of Max
# sum problem in a
# triangle
 
N = 3
 
# Function for finding maximum sum
def maxPathSum(tri, m, n):
 
    # loop for bottom-up calculation
    for i in range(m-1, -1, -1):
        for j in range(i+1):
 
            # for each element, check both
            # elements just below the number
            # and below right to the number
            # add the maximum of them to it
            if (tri[i+1][j] > tri[i+1][j+1]):
                tri[i][j] += tri[i+1][j]
            else:
                tri[i][j] += tri[i+1][j+1]
 
    # return the top element
    # which stores the maximum sum
    return tri[0][0]
 
# Driver program to test above function
 
tri = [[1, 0, 0],
       [4, 8, 0],
       [1, 5, 3]]
print(maxPathSum(tri, 2, 2))
 
# This code is contributed
# by Soumen Ghosh.

C#

// C# Program for Dynamic Programming
// implementation of Max sum problem
// in a triangle
using System;
 
class GFG {
     
    // Function for finding maximum sum
    static int maxPathSum(int [,]tri,
                          int m, int n)
    {
        // loop for bottom-up calculation
        for (int i = m - 1; i >= 0; i--)
        {
            for (int j = 0; j <= i; j++)
            {
                // for each element,
                // check both elements
                // just below the number
                // and below right to
                // the number add the
                // maximum of them to it
                if (tri[i + 1,j] >
                       tri[i + 1,j + 1])
                    tri[i,j] +=
                           tri[i + 1,j];
                else
                    tri[i,j] +=
                       tri[i + 1,j + 1];
            }
        }
     
        // return the top element
        // which stores the maximum sum
        return tri[0,0];
    }
     
    /* Driver program to test above
    functions */
    public static void Main ()
    {
        int [,]tri = { {1, 0, 0},
                        {4, 8, 0},
                        {1, 5, 3} };
                         
        Console.Write (
             maxPathSum(tri, 2, 2));
    }
}
 
// This code is contributed by nitin mittal.

PHP

<?php
// PHP program for Dynamic
// Programming implementation of
// Max sum problem in a triangle
 
// Function for finding
// maximum sum
function maxPathSum($tri, $m, $n)
{
    // loop for bottom-up
    // calculation
    for ( $i = $m - 1; $i >= 0; $i--)
    {
        for ($j = 0; $j <= $i; $j++)
        {
            // for each element, check
            // both elements just below
            // the number and below right
            // to the number add the maximum
            // of them to it
            if ($tri[$i + 1][$j] > $tri[$i + 1]
                                       [$j + 1])
                $tri[$i][$j] += $tri[$i + 1][$j];
            else
                $tri[$i][$j] += $tri[$i + 1]
                                    [$j + 1];
        }
    }
 
    // return the top element
    // which stores the maximum sum
    return $tri[0][0];
}
 
// Driver Code
$tri= array(array(1, 0, 0),
            array(4, 8, 0),
            array(1, 5, 3));
echo maxPathSum($tri, 2, 2);
 
// This code is contributed by ajit
?>

Javascript

<script>
// Javascript Program for Dynamic
// Programming implementation of
// Max sum problem in a triangle
    let N = 3;
       
    // Function for finding maximum sum
    function maxPathSum(tri, m, n)
    {
     
        // loop for bottom-up calculation
        for (let i = m - 1; i >= 0; i--)
        {
            for (let j = 0; j <= i; j++)
            {
             
                // for each element, check both
                // elements just below the number
                // and below right to the number
                // add the maximum of them to it
                if (tri[i + 1][j] > tri[i + 1][j + 1])
                    tri[i][j] += tri[i + 1][j];
                else
                    tri[i][j] += tri[i + 1][j + 1];
            }
        }
       
        // return the top element
        // which stores the maximum sum
        return tri[0][0];
    }
         
// Driver code   
    let tri = [[1, 0, 0],
                  [4, 8, 0],
                  [1, 5, 3]];
       document.write( maxPathSum(tri, 2, 2));
               
// This code is contributed by susmitakundugoaldanga.           
</script>
Producción

14

Análisis de Complejidad:

  • Complejidad de tiempo: O(m*n) donde m = número de filas y n = número de columnas
  • Complejidad espacial: O(1)

Este artículo es una contribución de Shivam Pradhan (anuj_charm) . Si te gusta GeeksforGeeks y te gustaría contribuir, también puedes escribir un artículo usando write.geeksforgeeks.org o enviar tu artículo por correo a review-team@geeksforgeeks.org. Vea su artículo que aparece en la página principal de GeeksforGeeks y ayude a otros Geeks.
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

Deja una respuesta

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