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.
  • HackerRank Home

    HackerRank

  • |
  • Prepare
  • Certify
  • Compete
  • Hiring developers?
  1. All Contests
  2. ProjectEuler+
  3. Project Euler #82: Path sum: three ways
  4. Discussions

Project Euler #82: Path sum: three ways

Problem
Submissions
Leaderboard
Discussions

    You are viewing a single comment's thread. Return to all comments →

  • vizzy205
    11 months ago+ 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)
        
    
    0|
    Permalink
  • Blog
  • Scoring
  • Environment
  • FAQ
  • About Us
  • Support
  • Careers
  • Terms Of Service
  • Privacy Policy