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 #82: Path sum: three ways
  4. Discussions

Project Euler #82: Path sum: three ways

  • vizzy205
     + 0 comments

    I rotated the matrix so the starting becomes the right side and then used normal dp and in the end calculation i just take the minimum of last column. Sow why is my logic failing. It only passes 2 test cases and wrong answer for others but why?

    import sys
l=[]
for _ in range(int(input())):
    l.append(list(map(int,input().strip().split(" "))))

n=len(l)
cost=[]

for i in range(n):
    cost.append(l[i][::-1])
#print(cost)

dp=[[0 for i in range(n)] for j in range(n)]

for i in range(n):
    dp[i][0]=dp[i-1][0]+cost[i][0]
    
for j in range(n):
    dp[0][j] = dp[0][j-1] + cost[0][j]   

for i in range(1,n):
    for j in range(1,n):
        dp[i][j]=min(dp[i-1][j],dp[i][j-1]) + cost[i][j]
        
#print(dp)      
minimum=sys.maxsize
   
for i in range(0,n-1):
    if minimum>dp[i][n-1]:
        minimum=dp[i][n-1]
        
print(minimum)