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