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.
Project Euler #18: Maximum path sum I
Project Euler #18: Maximum path sum I
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
Sort 62 Discussions, By:
Please Login in order to post a comment