Dada una estructura triangular de números, encuentre la suma mínima del camino de arriba a abajo. Cada paso se puede mover a los números adyacentes en la fila de abajo.
Ejemplos:
Input : 2 3 7 8 5 6 6 1 9 3 Output : 11 Explanation : 2 + 3 + 5 + 1 = 11 Input : 3 6 4 5 2 7 9 1 8 6 Output : 10 Explanation : 3 + 4 + 2 + 1 = 10
Enfoque ingenuo: pasar por el enfoque ingenuo recorriendo todos los caminos posibles. Pero, esto es costoso. Por lo tanto, use Programación Dinámica aquí para reducir la complejidad del tiempo.
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>>& A, int i, int j){
// Base Case
if(i == A.size() ){
return 0 ;
}
int mn ;
// Add current to the minimum of the next paths
mn = A[i][j] + min(helper(A, i+1,j), helper(A,i+1, j+1)) ;
//return minimum
return mn ;
}
int minSumPath(vector<vector<int>>& A) {
return helper(A, 0, 0) ;
}
/* Driver program to test above functions */
int main()
{
vector<vector<int> > A{ { 2 },
{ 3, 9 },
{ 1, 6, 7 } };
cout << minSumPath(A);
return 0;
}
Java
// Java program for
// Recursive implementation of
// Min sum path in a triangle
import java.io.*;
class GFG {
// Util function to find minimum sum for a path
static int helper(int A[][], int i, int j)
{
// Base Case
if(i == A.length){
return 0 ;
}
int mn ;
// Add current to the minimum of the next paths
mn = A[i][j] + Math.min(helper(A, i+1,j), helper(A,i+1, j+1)) ;
//return minimum
return mn ;
}
static int minSumPath(int A[][]) {
return helper(A, 0, 0) ;
}
/* Driver program to test above functions */
public static void main(String[] args)
{
int triangle [][] = { { 2 },
{ 3, 9 },
{ 1, 6, 7 } };
System.out.print(minSumPath(triangle));
}
}
// This code is contributed by Rohini Chandra
Python3
# Python3 program for # Recursion implementation of # Min Sum Path in a Triangle # Util function to find minimum sum for a path def helper(A, i, j): # Base Case if(i == len(A)): return 0 # Add current to the minimum of the next paths mn = A[i][j] + min(helper(A, i + 1, j), helper(A, i + 1, j + 1)) # return minimum return mn def minSumPath(A): return helper(A, 0, 0) # Driver program to test above functions A = [ [ 2 ], [ 3, 9 ], [ 1, 6, 7 ] ] print(minSumPath(A)) # This code is contributed by shinjanpatra.
Javascript
<script>
// JavaScript program for
// Recursion implementation of
// Min Sum Path in a Triangle
// Util function to find minimum sum for a path
function helper(A, i, j)
{
// Base Case
if(i == A.length )
{
return 0 ;
}
let mn ;
// Add current to the minimum of the next paths
mn = A[i][j] + Math.min(helper(A, i + 1,j), helper(A, i + 1, j + 1)) ;
// return minimum
return mn ;
}
function minSumPath(A)
{
return helper(A, 0, 0) ;
}
/* Driver program to test above functions */
let A = [ [ 2 ], [ 3, 9 ], [ 1, 6, 7 ] ];
document.write(minSumPath(A));
// This code is contributed by shinjanpatra.
</script>
Producción
6
Complejidad de tiempo: O(2 N*N ) donde N = número de filas y M = número de columnas
Espacio Auxiliar: O(N)
Hay dos formas de llegar a la solución:
1. Memoización: comenzando desde el Node superior, recorra recursivamente con cada Node, hasta que se calcule la ruta de acceso de ese Node. Y luego almacene el resultado en una array. Pero esto tomará espacio O (N ^ 2) para mantener la array.
Implementación del enfoque 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>>& A, int i, int j, vector<vector<int>>& dp){
// Base Case
if(i == A.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] = A[i][j] + min(helper(A, i+1,j, dp), helper(A,i+1, j+1, dp)) ;
}
int minSumPath(vector<vector<int>>& A) {
int n = A.size() ;
// Initializating of dp matrix
vector<vector<int>> dp(n, vector<int>(n, -1) ) ;
// calling helper function
return helper(A, 0, 0, dp) ;
}
/* Driver program to test above functions */
int main()
{
vector<vector<int> > A{ { 2 },
{ 3, 9 },
{ 1, 6, 7 } };
cout << minSumPath(A);
return 0;
}
Java
// Java program for
// Recursive implementation of
// Min sum path in a triangle
import java.io.*;
import java.util.Arrays;
class GFG {
// Function for finding miximum sum
public static int helper(int A[][], int i, int j, int dp[][])
{
if (i == A.length) {
return 0;
}
if (dp[i][j] != -1) return dp[i][j];
return dp[i][j] = A[i][j] + Math.min(helper(A, i+1, j, dp), helper(A, i+1, j + 1, dp));
}
public static int minSumPath(int A[][]) {
int n = A.length;
// Initializating of dp matrix
int dp[][] = new int[n][n];
for(int[] row : dp)
Arrays.fill(row,-1);
// calling helper function
return helper(A, 0, 0, dp) ;
}
/* Driver program to test above functions */
public static void main(String[] args)
{
int A [][] = { { 2 },
{ 3, 9 },
{ 1, 6, 7 } };
System.out.print(minSumPath(A));
}
}
// This code is contributed by Rohini Chandra
Python3
# Python program for Dynamic # Programming implementation of # Min Sum Path in a Triangle # Util function to find minimum sum for a path def helper(A, i, j, dp): # Base Case if(i == len(A)): 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 dp[i][j] = A[i][j] + min(helper(A, i+1,j, dp), helper(A,i+1, j+1, dp)) return dp[i][j] def minSumPath(A): n = len(A) # Initializating of dp matrix dp = [[-1]*n]*n # calling helper function return helper(A, 0, 0, dp) # Driver program to test above functions A = [ [ 2 ],[ 3, 9 ],[ 1, 6, 7 ] ] print(minSumPath(A)) # This code is contributed by shinjanpatra
Javascript
<script>
// JavaScript program for Dynamic
// Programming implementation of
// Min Sum Path in a Triangle
// Util function to find minimum sum for a path
function helper(A, i, j, dp)
{
// Base Case
if(i == A.length){
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] = A[i][j] + Math.min(helper(A, i+1,j, dp), helper(A,i+1, j+1, dp)) ;
}
function minSumPath(A) {
let n = A.length ;
// Initializating of dp matrix
let dp = new Array(n);
for(let i=0;i<n;i++){
dp[i] = new Array(n).fill(-1);
}
// calling helper function
return helper(A, 0, 0, dp) ;
}
/* Driver program to test above functions */
let A = [ [ 2 ],[ 3, 9 ],[ 1, 6, 7 ] ];
document.write(minSumPath(A));
// This code is contributed by shinjanpatra
</script>
Producción
6
Complejidad de tiempo: O(N*M) donde N = número de filas y M = número de columnas
Espacio Auxiliar: O(N 2 )
2. De abajo hacia arriba: comience desde los Nodes en la fila inferior; la suma de ruta mínima para estos Nodes son los valores de los propios Nodes. Y después de eso, la suma de ruta mínima en el i-ésimo Node de la fila k-ésima sería el mínimo de la suma de ruta de sus dos hijos + el valor del Node, es decir:
memo[k][i] = min( memo[k+1][i], memo[k+1][i+1]) + A[k][i];
O
simplemente configure memo como una array 1D y actualícelo,
esto también será eficiente en el espacio:
Para la fila k :
memo[i] = min( memo[i], memo[i+1]) + A[k][i];
A continuación se muestra la implementación del enfoque de programación dinámica 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 minSumPath(vector<vector<int> >& A)
{
// For storing the result in a 1-D array,
// and simultaneously updating the result.
int memo[A.size()];
int n = A.size() - 1;
// For the bottom row
for (int i = 0; i < A[n].size(); i++)
memo[i] = A[n][i];
// Calculation of the remaining rows,
// in bottom up manner.
for (int i = A.size() - 2; i >= 0; i--)
for (int j = 0; j < A[i].size(); j++)
memo[j] = A[i][j] + min(memo[j],
memo[j + 1]);
// return the top element
return memo[0];
}
/* Driver program to test above functions */
int main()
{
vector<vector<int> > A{ { 2 },
{ 3, 9 },
{ 1, 6, 7 } };
cout << minSumPath(A);
return 0;
}
Java
// Java program for Dynamic
// Programming implementation of
// Min Sum Path in a Triangle
import java.io.*;
import java.util.*;
class GFG
{
static int A[][] = {{2},
{3, 9},
{1, 6, 7}};
// Util function to find
// minimum sum for a path
static int minSumPath()
{
// For storing the result
// in a 1-D array, and
// simultaneously updating
// the result.
int []memo = new int[A.length];
int n = A.length - 1;
// For the bottom row
for (int i = 0;
i < A[n].length; i++)
memo[i] = A[n][i];
// Calculation of the
// remaining rows, in
// bottom up manner.
for (int i = A.length - 2;
i >= 0; i--)
for (int j = 0;
j < A[i].length; j++)
memo[j] = A[i][j] +
(int)Math.min(memo[j],
memo[j + 1]);
// return the
// top element
return memo[0];
}
// Driver Code
public static void main(String args[])
{
System.out.print(minSumPath());
}
}
// This code is contributed by
// Manish Shaw (manishshaw1)
Python3
# Python3 program for Dynamic # Programming implementation of # Min Sum Path in a Triangle # Util function to find # minimum sum for a path def minSumPath(A): # For storing the result in # a 1-D array, and simultaneously # updating the result. memo = [None] * len(A) n = len(A) - 1 # For the bottom row for i in range(len(A[n])): memo[i] = A[n][i] # Calculation of the # remaining rows, # in bottom up manner. for i in range(len(A) - 2, -1,-1): for j in range( len(A[i])): memo[j] = A[i][j] + min(memo[j], memo[j + 1]); # return the top element return memo[0] # Driver Code A = [[ 2 ], [3, 9 ], [1, 6, 7 ]] print(minSumPath(A)) # This code is contributed # by ChitraNayal
C#
// C# program for Dynamic
// Programming implementation of
// Min Sum Path in a Triangle
using System;
using System.Collections.Generic;
using System.Linq;
class GFG {
// Util function to find
// minimum sum for a path
static int minSumPath(ref List<List<int>> A)
{
// For storing the result in a 1-D array,
// and simultaneously updating the result.
int []memo = new int[A.Count];
int n = A.Count - 1;
// For the bottom row
for (int i = 0; i < A[n].Count; i++)
memo[i] = A[n][i];
// Calculation of the remaining rows,
// in bottom up manner.
for (int i = A.Count - 2; i >= 0; i--)
for (int j = 0; j < A[i + 1].Count - 1; j++)
memo[j] = A[i][j] +
(int)Math.Min(memo[j],
memo[j + 1]);
// return the top element
return memo[0];
}
// Driver Code
public static void Main()
{
List<List<int>> A = new List<List<int>>();
A.Add(new List<int> {2});
A.Add(new List<int> {3, 9});
A.Add(new List<int> {1, 6, 7});
Console.WriteLine(minSumPath(ref A));
}
}
// This code is contributed by
// Manish Shaw (manishshaw1)
PHP
<?php
// PHP program for Dynamic
// Programming implementation of
// Min Sum Path in a Triangle
// Util function to find
// minimum sum for a path
function minSumPath(&$A)
{
// For storing the result
// in a 1-D array, and
// simultaneously updating
// the result.
$memo = array();
for ($i = 0; $i < count($A); $i++)
$memo[$i] = 0;
$n = count($A) - 1;
// For the bottom row
for ($i = 0;
$i < count($A[$n]); $i++)
$memo[$i] = $A[$n][$i];
// Calculation of
// the remaining rows,
// in bottom up manner.
for ($i = count($A) - 2; $i >= 0; $i--)
for ($j = 0;
$j < count($A[$i + 1]) - 1; $j++)
$memo[$j] = $A[$i][$j] +
min($memo[$j],
$memo[$j + 1]);
// return the
// top element
return $memo[0];
}
// Driver Code
$A = array(array(2),
array(3, 9),
array(1, 6, 7));
echo (minSumPath($A));
// This code is contributed
// by Manish Shaw(manishshaw1)
?>
Javascript
<script>
// JavaScript program for Dynamic
// Programming implementation of
// Min Sum Path in a Triangle
let A = [[2], [3, 9], [1, 6, 7]];
// Util function to find
// minimum sum for a path
function minSumPath()
{
// For storing the result
// in a 1-D array, and
// simultaneously updating
// the result.
let memo = [];
let n = A.length - 1;
// For the bottom row
for(let i = 0; i < A[n].length; i++)
memo[i] = A[n][i];
// Calculation of the
// remaining rows, in
// bottom up manner.
for(let i = A.length - 2; i >= 0; i--)
for(let j = 0;
j < A[i].length; j++)
memo[j] = A[i][j] +
Math.min(memo[j],
memo[j + 1]);
// Return the
// top element
return memo[0];
}
// Driver code
document.write(minSumPath());
// This code is contributed by splevel62
</script>
Producción
6
Complejidad de tiempo: O(N*M) donde N = número de filas y M = número de columnas
Espacio Auxiliar: O(N)
Enfoque de optimización del espacio: en lugar de usar otra array, podemos almacenar los resultados en la misma array.
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 minSumPath(vector<vector<int> >& A)
{
int n = A.size();
int ans = 0;
for (int i = 0; i < n; i++) {
int minimum = INT_MAX;
// the maximum element in each row is equal to row
// number
for (int j = 0; j <= i; j++) {
if (i == 0 && j == 0) {
// if both zero means first element
minimum = min(minimum, A[i][j]);
continue;
}
// if j==i means the last element so we will not
// calculate up of the last element
if (j == i) {
A[i][j] = A[i][j] + A[i - 1][j - 1];
minimum = min(minimum, A[i][j]);
continue;
}
// The value at i,j will be calculated using
// [i-1][j-1] or either [i-1][j] either the
// element just above or the left of the upper
// row
int up = A[i][j], down = A[i][j];
if (j > 0) {
up += A[i - 1][j - 1];
}
else {
up = INT_MAX;
}
down += A[i - 1][j];
A[i][j] = min(up, down);
// This minimum is to keep track of the minimum
// from each row so that we don't have to
// calculate it separately
minimum = min(minimum, A[i][j]);
}
ans = minimum;
}
return ans;
}
/* Driver program to test above functions */
int main()
{
vector<vector<int> > A{ { 2 }, { 3, 9 }, { 1, 6, 7 } };
cout << minSumPath(A);
return 0;
}
Java
// Java program for Dynamic
// Programming implementation of
// Min Sum Path in a Triangle
import java.io.*;
import java.util.*;
class GFG {
static int A[][] = { { 2 }, { 3, 9 }, { 1, 6, 7 } };
// Util function to find
// minimum sum for a path
static int minSumPath()
{
int n = A.length;
int ans = 0;
for (int i = 0; i < n; i++) {
int minimum = Integer.MAX_VALUE;
// the maximum element in each row is equal to
// row number
for (int j = 0; j <= i; j++) {
if (i == 0 && j == 0) {
// if both zero means first element
minimum = Math.min(minimum, A[i][j]);
continue;
}
// if j==i means the last element so we will
// not calculate up of the last element
if (j == i) {
A[i][j] = A[i][j] + A[i - 1][j - 1];
minimum = Math.min(minimum, A[i][j]);
continue;
}
// The value at i,j will be calculated using
// [i-1][j-1] or either [i-1][j] either the
// element just above or the left in the
// upper row
int up = A[i][j], down = A[i][j];
if (j > 0) {
up += A[i - 1][j - 1];
}
else {
up = Integer.MAX_VALUE;
}
down += A[i - 1][j];
A[i][j] = Math.min(up, down);
// This minimum is to keep track of the
// minimum
// from each row so that we don't have to
// calculate it separately
minimum = Math.min(minimum, A[i][j]);
}
ans = minimum;
}
return ans;
}
// Driver Code
public static void main(String args[])
{
System.out.print(minSumPath());
}
}
// This code is contributed by
// Manish Shaw (manishshaw1)
Producción:
6
Complejidad de tiempo: O(N*M) donde N = número de filas y M = número de columnas
Espacio Auxiliar: O(1)
Publicación traducida automáticamente
Artículo escrito por himanshu batra y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA