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.
  • Practice
  • Certification
  • Compete
  • Career Fair
  • Hiring developers?
  1. All Contests
  2. ProjectEuler+
  3. Project Euler #18: Maximum path sum I
  4. Discussions

Project Euler #18: Maximum path sum I

Problem
Submissions
Leaderboard
Discussions

Sort 62 Discussions, By:

votes

Please Login in order to post a comment

  • AlanThomas 4 years ago+ 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.

    15|
    Permalink
  • bladekiller97 4 years ago+ 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;
    }
    
    12|
    Permalink
  • iamprayush 2 years ago+ 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])
    
    8|
    Permalink
  • abdulrahuman5196 5 years ago+ 0 comments

    Wonderful dynamic programming problem

    6|
    Permalink
  • decoder_304 3 years ago+ 0 comments

    Worst Explanation for a problem.

    4|
    Permalink
Load more conversations

Need Help?


View top submissions
  • Contest Calendar
  • Blog
  • Scoring
  • Environment
  • FAQ
  • About Us
  • Support
  • Careers
  • Terms Of Service
  • Privacy Policy
  • Request a Feature