Números dados en forma de triángulo invertido. Al comenzar en la parte inferior del triángulo y pasar a los números adyacentes en la fila de arriba, encuentre el total máximo de abajo hacia arriba.
Ejemplos:
Input : 1 5 3
4 8
1
Output : 14
Input : 8 5 9 3
2 4 6
7 4
3
Output : 23
Método 1: recursividad
En el artículo anterior vimos un planteamiento del problema donde el triángulo no está invertido.
Aquí también usaremos el mismo enfoque para encontrar la solución del problema como se discutió en el artículo anterior .
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 se parece a la ruta de costo mínimo .
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 INT_MIN;
}
if(i == 0 ){
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, 5, 3 },
{ 4, 8, 0 },
{ 1, 0, 0 } };
cout << maxPathSum(tri, 2, 0, 2, 2);
return 0;
}
Producción
14
Análisis de Complejidad:
- Complejidad del tiempo: O(2 N*N )
- Complejidad espacial: O(N)
Método 2: DP de arriba hacia abajo
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.
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, vector<vector<int>> &dp){
if(j == col ){
return INT_MIN;
}
if(i == 0 ){
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, 5, 3 },
{ 4, 8, 0 },
{ 1, 0, 0 } };
vector<vector<int>> dp(N, vector<int>(N, -1) ) ;
cout << maxPathSum(tri, 2, 0, 2, 2, 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 3: DP de abajo hacia arriba
Aplicando, DP de forma ascendente, deberíamos resolver nuestro problema como:
Ejemplo:
8 5 9 3 2 4 6 7 4 3 Step 1 : 8 5 9 3 2 4 6 0 7 4 0 0 3 0 0 0 Step 2 : 8 5 9 3 2 4 6 0 10 7 0 0 Step 3 : 8 5 9 3 12 14 13 0 Step 4: 20 19 23 16 Output : 23
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program 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 ans = 0;
// Loop for bottom-up calculation
for (int i = N - 2; i >= 0; i--) {
for (int j = 0; j < N - i; j++) {
// For each element, check both
// elements just below the number
// and below left to the number
// add the maximum of them to it
if (j - 1 >= 0)
tri[i][j] += max(tri[i + 1][j],
tri[i + 1][j - 1]);
else
tri[i][j] += tri[i + 1][j];
ans = max(ans, tri[i][j]);
}
}
// Return the maximum sum
return ans;
}
// Driver Code
int main()
{
int tri[N][N] = { { 1, 5, 3 },
{ 4, 8, 0 },
{ 1, 0, 0 } };
cout << maxPathSum(tri);
return 0;
}
Java
// Java program implementation of
// Max sum problem in a triangle
class GFG
{
static int N = 3;
// Function for finding maximum sum
static int maxPathSum(int tri[][])
{
int ans = 0;
// Loop for bottom-up calculation
for (int i = N - 2; i >= 0; i--)
{
for (int j = 0; j < N - i; j++)
{
// For each element, check both
// elements just below the number
// and below left to the number
// add the maximum of them to it
if (j - 1 >= 0)
tri[i][j] += Math.max(tri[i + 1][j],
tri[i + 1][j - 1]);
else
tri[i][j] += tri[i + 1][j];
ans = Math.max(ans, tri[i][j]);
}
}
// Return the maximum sum
return ans;
}
// Driver Code
public static void main(String []args)
{
int tri[][] = { { 1, 5, 3 },
{ 4, 8, 0 },
{ 1, 0, 0 } };
System.out.println(maxPathSum(tri));
}
}
// This code is contributed by ihritik
Python3
# Python program implementation of # Max sum problem in a triangle N = 3 # Function for finding maximum sum def maxPathSum( tri ): ans = 0; # Loop for bottom-up calculation for i in range(N - 2, -1, -1): for j in range(0 , N - i): # For each element, check both # elements just below the number # and below left to the number # add the maximum of them to it if (j - 1 >= 0): tri[i][j] += max(tri[i + 1][j], tri[i + 1][j - 1]); else: tri[i][j] += tri[i + 1][j]; ans = max(ans, tri[i][j]); # Return the maximum sum return ans # Driver Code tri = [ [ 1, 5, 3 ], [ 4, 8, 0 ], [ 1, 0, 0 ] ] print(maxPathSum(tri)) # This code is contributed by ihritik
C#
// C# program implementation of
// Max sum problem in a triangle
using System;
class GFG
{
static int N = 3;
// Function for finding maximum sum
static int maxPathSum(int [,]tri)
{
int ans = 0;
// Loop for bottom-up calculation
for (int i = N - 2; i >= 0; i--)
{
for (int j = 0; j < N - i; j++)
{
// For each element, check both
// elements just below the number
// and below left to the number
// add the maximum of them to it
if (j - 1 >= 0)
tri[i, j] += Math.Max(tri[i + 1, j],
tri[i + 1, j - 1]);
else
tri[i, j] += tri[i + 1, j];
ans = Math.Max(ans, tri[i, j]);
}
}
// Return the maximum sum
return ans;
}
// Driver Code
public static void Main()
{
int[,] tri = { { 1, 5, 3 },
{ 4, 8, 0 },
{ 1, 0, 0 } };
Console.WriteLine(maxPathSum(tri));
}
}
// This code is contributed by ihritik
PHP
<?php
// PHP program implementation of
// Max sum problem in a triangle
$N = 3;
// Function for finding maximum sum
function maxPathSum($tri)
{
global $N;
$ans = 0;
// Loop for bottom-up calculation
for ($i = $N - 2; $i >= 0; $i--)
{
for ($j = 0; $j < $N - $i; $j++)
{
// For each element, check both
// elements just below the number
// and below left to the number
// add the maximum of them to it
if ($j - 1 >= 0)
$tri[$i][$j] += max($tri[$i + 1][$j],
$tri[$i + 1][$j - 1]);
else
$tri[$i][$j] += $tri[$i + 1][$j];
$ans = max($ans, $tri[$i][$j]);
}
}
// Return the maximum sum
return $ans;
}
// Driver Code
$tri = array(array( 1, 5, 3 ),
array( 4, 8, 0 ),
array( 1, 0, 0 ));
echo maxPathSum($tri);
// This code is contributed by chandan_jnu
?>
Javascript
<script>
//Javascript program implementation of
// Max sum problem in a triangle
N = 3;
// Function for finding maximum sum
function maxPathSum(tri)
{
var ans = 0;
// Loop for bottom-up calculation
for (var i = N - 2; i >= 0; i--) {
for (var j = 0; j < N - i; j++) {
// For each element, check both
// elements just below the number
// and below left to the number
// add the maximum of them to it
if (j - 1 >= 0)
tri[i][j] += Math.max(tri[i + 1][j],
tri[i + 1][j - 1]);
else
tri[i][j] += tri[i + 1][j];
ans = Math.max(ans, tri[i][j]);
}
}
// Return the maximum sum
return ans;
}
var tri = [[ 1, 5, 3 ],
[ 4, 8, 0 ],
[ 1, 0, 0 ]];
document.write(maxPathSum(tri));
//This code is contributed by SoumikMondal
</script>
Producción
14
Complejidad temporal: O(N 2 )
Espacio Auxiliar: O(1)
Publicación traducida automáticamente
Artículo escrito por Sanjit_Prasad y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA