We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
  1. All Contests
  2. ProjectEuler+
  3. Project Euler #18: Maximum path sum I
  4. Discussions

Project Euler #18: Maximum path sum I

Sort 62 Discussions, By:

  • AlanThomas + 0 comments

    People who were able to solve only TestCase0 did not understand the question clearly. Consider the triangle: 

        1
   2 10
  6 5 10
 50 5 6 10

    The correct path is 1->2->6->50 and the answer should be 1+2+6+50=59. If we use greedy, the path would be 1->10->10->10, and answer would be 31, which is smaller than 59. We should consider the largest possible sum out of all possible sum(satisfying the condition of moving to adjacent numbers only). Solving with dynamic programming is recommended. Question67 is the same problem with larger value of n.

  • bladekiller97 + 0 comments

    Here is my sol :

    #include <iostream>
#include <vector>
using namespace std;

int main() {
	
	int t;
	cin >> t;
	
	for (int i = 1; i <= t ; i++){
		int n, val;
		cin >> n;
		
		vector< vector<int> > dp(n);
		
		for (int i = 0 ; i < n; i++){
			for (int j = 0; j <= i; j++){
				cin >> val;
				dp[i].push_back(val);
			}
		}
		
		for (int i = n - 2 ; i >= 0; i--){
			for (int j = 0; j <= i; j++){
				dp[i][j] += max(dp[i + 1][j], dp[i + 1][j + 1]);	
			}
		}
		
		cout << dp[0][0] << endl;	
	}
	
	return 0;
}

  • iamprayush + 0 comments

    Elegant python solution:

    for _ in range(int(input())):
    n = int(input())
    s = []
    for i in range(n):
        s.append(list(map(int, input().split())))
    
    row = n-2
    while row >= 0:
        for i in range(len(s[row])):
            s[row][i] += max(s[row+1][i], s[row+1][i+1])
        row -= 1
    print(s[0][0])

  • abdulrahuman5196 + 0 comments

    Wonderful dynamic programming problem

  • decoder_304 + 0 comments

    Worst Explanation for a problem.

Load more conversations