Максимальная сумма путей в треугольнике.
Мы задали числа в форме треугольника, начиная с вершины треугольника и переходя к соседним числам в строке ниже, найдите максимальную сумму сверху вниз.
Примеры :
Вход : 3 7 4 2 4 6 8 5 9 3 Выход: 23 Объяснение: 3 + 7 + 4 + 9 = 23 Вход : 8 -4 4 2 2 6 1 1 1 1 Выход: 19 Пояснение: 8 + 4 + 6 + 1 = 19
Мы можем пройти через грубую силу, проверив все возможные пути, но это занимает много времени, поэтому мы должны попытаться решить эту проблему с помощью динамического программирования, которое снижает временную сложность.
Если мы должны сдвинуть влево каждый элемент и поставить 0 в каждую пустую позицию, чтобы сделать его обычной матрицей, тогда наша проблема будет выглядеть как путь с минимальной стоимостью.
Итак, после преобразования наших входных элементов треугольника в регулярную матрицу мы должны применить динамическую программную концепцию, чтобы найти максимальную сумму путей.
Применяя DP снизу вверх, мы должны решить нашу проблему следующим образом:
Пример:
3 7 4 2 4 6 8 5 9 3 Шаг 1 : 3 0 0 0 7 4 0 0 2 4 6 0 8 5 9 3 Шаг 2 : 3 0 0 0 7 4 0 0 10 13 15 0 Шаг 3 : 3 0 0 0 20 19 0 0 Шаг 4: 23 0 0 0 вывод: 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> |
Выход :
14
Эта статья предоставлена Шивамом Прадханом (anuj_charm). Если вам нравится GeeksforGeeks, и вы хотели бы внести свой вклад, вы также можете написать статью на сайте deposit.geeksforgeeks.org или отправить свою статью по электронной почте: grant@geeksforgeeks.org. Посмотрите, как ваша статья появляется на главной странице GeeksforGeeks, и помогите другим гикам.
Пожалуйста, напишите комментарии, если вы обнаружите что-то неправильное, или вы хотите поделиться дополнительной информацией по теме, обсужденной выше.
Вниманию читателя! Не прекращайте учиться сейчас. Освойте все важные концепции DSA с помощью самостоятельного курса DSA по приемлемой для студентов цене и будьте готовы к работе в отрасли. Чтобы завершить подготовку от изучения языка к DS Algo и многому другому, см. Полный курс подготовки к собеседованию .
Если вы хотите посещать живые занятия с отраслевыми экспертами, пожалуйста, обращайтесь к Geeks Classes Live и Geeks Classes Live USA.