Dado un triángulo rectángulo de números, encuentre el mayor de la suma de los números que aparecen en los caminos que comienzan desde la parte superior hacia la base, de modo que en cada camino el siguiente número se ubique directamente debajo o debajo y un lugar a -la derecha.
Ejemplos:
Input : 1
1 2
4 1 2
2 3 1 1
Output : 9
Explanation : 1 + 1 + 4 + 3
Input : 2
4 1
1 2 7
Output : 10
Explanation : 2 + 1 + 7
Método 1: recursividad
La idea es encontrar la suma más grande que termina en cada celda de la última fila y devolver un máximo de estas sumas. Podemos calcular recursivamente estas sumas considerando recursivamente las dos celdas anteriores.
C++
// C++ program for
// Recursion implementation of
// Min Sum Path in a Triangle
#include <bits/stdc++.h>
using namespace std;
// Util function to find minimum sum for a path
int helper(vector<vector<int>>& tri, int i, int j){
// Base Case
if(i == tri.size() ){
return 0 ;
}
int mx ;
// Add current to the maximum of the next paths
mx = tri[i][j] + max(helper(tri, i+1,j), helper(tri,i+1, j+1)) ;
//return maximum
return mx ;
}
int maxSumPath(vector<vector<int>>& tri) {
return helper(tri, 0, 0) ;
}
/* Driver program to test above functions */
int main()
{
vector<vector<int> > tri{ { 1 },
{ 2, 1 },
{ 3, 3, 2 } };
cout << maxSumPath(tri);
return 0;
}
Java
// Java program for
// Recursion implementation of
// Min Sum Path in a Triangle
import java.io.*;
class GFG
{
// Util function to find minimum sum for a path
public static int helper(int tri[][], int i, int j)
{
// Base Case
if (i == tri.length) {
return 0;
}
int mx;
// Add current to the maximum of the next paths
mx = tri[i][j]
+ Math.max(helper(tri, i + 1, j),
helper(tri, i + 1, j + 1));
// return maximum
return mx;
}
public static int maxSumPath(int tri[][])
{
return helper(tri, 0, 0);
}
/* Driver program to test above functions */
public static void main(String[] args)
{
int tri[][] = { { 1 }, { 2, 1 }, { 3, 3, 2 } };
System.out.print(maxSumPath(tri));
}
}
// This code is contributed by Rohit Pradhan
Producción
6
Análisis de Complejidad:
- Complejidad de tiempo: O(2N*N) donde N = número de filas y M = número de columnas
- Espacio Auxiliar: O(N)
Método 2: Programación Dinámica – Enfoque de arriba hacia abajo
Como hay subproblemas superpuestos, usamos programación dinámica para encontrar la suma máxima que termina en una celda particular de la última fila.
A continuación se muestra la implementación de la idea anterior.
C++
// C++ program for Dynamic
// Programming implementation of
// Min Sum Path in a Triangle
#include <bits/stdc++.h>
using namespace std;
// Util function to find minimum sum for a path
int helper(vector<vector<int>>& tri, int i, int j, vector<vector<int>>& dp){
// Base Case
if(i == tri.size() ){
return 0 ;
}
// To avoid solving overlapping subproblem
if(dp[i][j] != -1){
return dp[i][j] ;
}
// Add current to the minimum of the next paths
// and store it in dp matrix
return dp[i][j] = tri[i][j] + max(helper(tri, i+1,j, dp), helper(tri,i+1, j+1, dp)) ;
}
int maxSumPath(vector<vector<int>>& tri) {
int n = tri.size() ;
// Initializating of dp matrix
vector<vector<int>> dp(n, vector<int>(n, -1) ) ;
// calling helper function
return helper(tri, 0, 0, dp) ;
}
/* Driver program to test above functions */
int main()
{
vector<vector<int> > tri{ { 1 },
{ 2, 1 },
{ 3, 3, 2 } };
cout << maxSumPath(tri);
return 0;
}
Producción
6
Análisis de Complejidad:
- Complejidad de tiempo: O(N*M) donde N = número de filas y M = número de columnas
- Espacio Auxiliar: O(N 2 )
Método 3: Programación dinámica: enfoque ascendente
Como hay subproblemas superpuestos, usamos programación dinámica para encontrar la suma máxima que termina en una celda particular de la última fila. A continuación se muestra la implementación de la idea anterior.
C++
// C++ program for Dynamic
// Programming implementation of
// Min Sum Path in a Triangle
#include <bits/stdc++.h>
using namespace std;
// Util function to find minimum sum for a path
int helper(vector<vector<int>>& tri, int i, int j, vector<vector<int>>& dp){
int n = tri.size() ;
// 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] ;
}
int maxSumPath(vector<vector<int>>& tri) {
int n = tri.size() ;
// Initializating of dp matrix
vector<vector<int>> dp(n, vector<int>(n, -1) ) ;
// calling helper function
return helper(tri, 0, 0, dp) ;
}
/* Driver program to test above functions */
int main()
{
vector<vector<int> > tri{ { 1 },
{ 2, 1 },
{ 3, 3, 2 } };
cout << maxSumPath(tri);
return 0;
}
Producción
6
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 de tamaño m*n. Almacenará todos los resultados.
Solo necesitamos el mínimo de fila triangular de la fila inferior inmediata
Entonces, usando este enfoque, podemos optimizar el espacio de O (m * n) a O (n).
El enfoque sigue siendo el mismo que el del Método 3.
C++
// C++ program for Dynamic
// Programming implementation of
// Min Sum Path in a Triangle
#include <bits/stdc++.h>
using namespace std;
// Util function to find minimum sum for a path
int helper(vector<vector<int>>& tri, int i, int j, vector<vector<int>>& dp){
int n = tri.size() ;
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] ;
}
int maxSumPath(vector<vector<int>>& tri) {
int n = tri.size() ;
// Initializating of dp matrix
vector<vector<int>> dp(n, vector<int>(n, -1) ) ;
// calling helper function
return helper(tri, 0, 0, dp) ;
}
/* Driver program to test above functions */
int main()
{
vector<vector<int> > tri{ { 1 },
{ 2, 1 },
{ 3, 3, 2 } };
cout << maxSumPath(tri);
return 0;
}
Producción
6
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 (cambio de la array de entrada)
C++
// C++ program to print maximum sum
// in a right triangle of numbers
#include<bits/stdc++.h>
using namespace std;
// function to find maximum sum path
int maxSum(int tri[][3], int n)
{
// Adding the element of row 1 to both the
// elements of row 2 to reduce a step from
// the loop
if (n > 1)
tri[1][1] = tri[1][1] + tri[0][0];
tri[1][0] = tri[1][0] + tri[0][0];
// Traverse remaining rows
for(int i = 2; i < n; i++) {
tri[i][0] = tri[i][0] + tri[i-1][0];
tri[i][i] = tri[i][i] + tri[i-1][i-1];
//Loop to traverse columns
for (int j = 1; j < i; j++){
// Checking the two conditions,
// directly below and below right.
// Considering the greater one
// tri[i] would store the possible
// combinations of sum of the paths
if (tri[i][j] + tri[i-1][j-1] >=
tri[i][j] + tri[i-1][j])
tri[i][j] = tri[i][j] + tri[i-1][j-1];
else
tri[i][j] = tri[i][j]+tri[i-1][j];
}
}
// array at n-1 index (tri[i]) stores
// all possible adding combination, finding
// the maximum one out of them
int max=tri[n-1][0];
for(int i=1;i<n;i++)
{
if(max<tri[n-1][i])
max=tri[n-1][i];
}
return max;
}
// driver program
int main(){
int tri[3][3] = {{1}, {2,1}, {3,3,2}};
cout<<maxSum(tri, 3);
return 0;
}
Java
// Java program to print maximum sum
// in a right triangle of numbers
class GFG
{
// function to find maximum sum path
static int maxSum(int tri[][], int n)
{
// Adding the element of row 1 to both the
// elements of row 2 to reduce a step from
// the loop
if (n > 1)
tri[1][1] = tri[1][1] + tri[0][0];
tri[1][0] = tri[1][0] + tri[0][0];
// Traverse remaining rows
for(int i = 2; i < n; i++) {
tri[i][0] = tri[i][0] + tri[i-1][0];
tri[i][i] = tri[i][i] + tri[i-1][i-1];
//Loop to traverse columns
for (int j = 1; j < i; j++){
// Checking the two conditions,
// directly below and below right.
// Considering the greater one
// tri[i] would store the possible
// combinations of sum of the paths
if (tri[i][j] + tri[i-1][j-1] >=
tri[i][j] + tri[i-1][j])
tri[i][j] = tri[i][j]
+ tri[i-1][j-1];
else
tri[i][j] = tri[i][j]
+ tri[i-1][j];
}
}
// array at n-1 index (tri[i]) stores
// all possible adding combination,
// finding the maximum one out of them
int max = tri[n-1][0];
for(int i = 1; i < n; i++)
{
if(max < tri[n-1][i])
max = tri[n-1][i];
}
return max;
}
// Driver code
public static void main (String[] args)
{
int tri[][] = {{1}, {2,1}, {3,3,2}};
System.out.println(maxSum(tri, 3));
}
}
// This code is contributed by Anant Agarwal.
Python3
# Python program to print maximum sum # in a right triangle of numbers. # tri[][] is a 2D array that stores the # triangle, n is number of lines or rows. def maxSum(tri, n): # Adding the element of row 1 to both the # elements of row 2 to reduce a step from # the loop if n > 1: tri[1][1] = tri[1][1]+tri[0][0] tri[1][0] = tri[1][0]+tri[0][0] # Traverse remaining rows for i in range(2, n): tri[i][0] = tri[i][0] + tri[i-1][0] tri[i][i] = tri[i][i] + tri[i-1][i-1] # Loop to traverse columns for j in range(1, i): # Checking the two conditions, directly below # and below right. Considering the greater one # tri[i] would store the possible combinations # of sum of the paths if tri[i][j]+tri[i-1][j-1] >= tri[i][j]+tri[i-1][j]: tri[i][j] = tri[i][j] + tri[i-1][j-1] else: tri[i][j] = tri[i][j]+tri[i-1][j] # array at n-1 index (tri[i]) stores all possible # adding combination, finding the maximum one # out of them print (max(tri[n-1])) # driver program tri = [[1], [2,1], [3,3,2]] maxSum(tri, 3)
C#
// C# program to print
// maximum sum in a right
// triangle of numbers
using System;
class GFG
{
// function to find
// maximum sum path
static int maxSum(int [,]tri,
int n)
{
// Adding the element of row 1
// to both the elements of row 2
// to reduce a step from the loop
if (n > 1)
tri[1, 1] = tri[1, 1] +
tri[0, 0];
tri[1, 0] = tri[1, 0] +
tri[0, 0];
// Traverse remaining rows
for(int i = 2; i < n; i++)
{
tri[i, 0] = tri[i, 0] +
tri[i - 1, 0];
tri[i, i] = tri[i, i] +
tri[i - 1, i - 1];
//Loop to traverse columns
for (int j = 1; j < i; j++)
{
// Checking the two conditions,
// directly below and below right.
// Considering the greater one
// tri[i] would store the possible
// combinations of sum of the paths
if (tri[i, j] + tri[i - 1, j - 1] >=
tri[i, j] + tri[i - 1, j])
tri[i, j] = tri[i, j] +
tri[i - 1, j - 1];
else
tri[i, j] = tri[i, j] +
tri[i - 1, j];
}
}
// array at n-1 index (tri[i])
// stores all possible adding
// combination, finding the
// maximum one out of them
int max = tri[n - 1, 0];
for(int i = 1; i < n; i++)
{
if(max < tri[n - 1, i])
max = tri[n - 1, i];
}
return max;
}
// Driver Code
public static void Main ()
{
int [,]tri = {{1,0,0},
{2,1,0},
{3,3,2}};
Console.Write(maxSum(tri, 3));
}
}
// This code is contributed by ajit.
PHP
<?php
// PHP program to print maximum sum
// in a right triangle of numbers
// function to find maximum sum path
function maxSum($tri, $n)
{
// Adding the element of row 1
// to both the elements of row
// 2 to reduce a step from the loop
if ($n > 1)
$tri[1][1] = $tri[1][1] + $tri[0][0];
$tri[1][0] = $tri[1][0] + $tri[0][0];
// Traverse remaining rows
for($i = 2; $i < $n; $i++)
{
$tri[$i][0] = $tri[$i][0] +
$tri[$i - 1][0];
$tri[$i][$i] = $tri[$i][$i] +
$tri[$i - 1][$i - 1];
//Loop to traverse columns
for ($j = 1; $j < $i; $j++)
{
// Checking the two conditions,
// directly below and below right.
// Considering the greater one
// tri[i] would store the possible
// combinations of sum of the paths
if ($tri[$i][$j] + $tri[$i - 1][$j - 1] >=
$tri[$i][$j] + $tri[$i - 1][$j])
$tri[$i][$j] = $tri[$i][$j] +
$tri[$i - 1][$j - 1];
else
$tri[$i][$j] = $tri[$i][$j] +
$tri[$i - 1][$j];
}
}
// array at n-1 index (tri[i])
// stores all possible adding
// combination, finding the
// maximum one out of them
$max = $tri[$n - 1][0];
for($i = 1; $i < $n; $i++)
{
if($max < $tri[$n - 1][$i])
$max = $tri[$n - 1][$i];
}
return $max;
}
// Driver Code
$tri = array(array(1),
array(2,1),
array(3,3,2));
echo maxSum($tri, 3);
// This code is contributed by ajit
?>
Javascript
<script>
// Javascript program to print maximum sum
// in a right triangle of numbers
// function to find maximum sum path
function maxSum(tri, n)
{
// Adding the element of row 1 to both the
// elements of row 2 to reduce a step from
// the loop
if (n > 1)
tri[1][1] = tri[1][1] + tri[0][0];
tri[1][0] = tri[1][0] + tri[0][0];
// Traverse remaining rows
for(let i = 2; i < n; i++) {
tri[i][0] = tri[i][0] + tri[i-1][0];
tri[i][i] = tri[i][i] + tri[i-1][i-1];
// Loop to traverse columns
for (let j = 1; j < i; j++){
// Checking the two conditions,
// directly below and below right.
// Considering the greater one
// tri[i] would store the possible
// combinations of sum of the paths
if (tri[i][j] + tri[i-1][j-1] >=
tri[i][j] + tri[i-1][j])
tri[i][j] = tri[i][j]
+ tri[i-1][j-1];
else
tri[i][j] = tri[i][j]
+ tri[i-1][j];
}
}
// array at n-1 index (tri[i]) stores
// all possible adding combination,
// finding the maximum one out of them
let max = tri[n-1][0];
for(let i = 1; i < n; i++)
{
if(max < tri[n-1][i])
max = tri[n-1][i];
}
return max;
}
let tri = [[1], [2,1], [3,3,2]];
document.write(maxSum(tri, 3));
</script>
Producción
6
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 Harshit Agrawal . 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