Advertisement
viligen

move down_right_DP

Aug 10th, 2022
475
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Python 0.98 KB | None | 0 0
  1. from collections import deque
  2.  
  3. rows = int(input())
  4. cols = int(input())
  5.  
  6. matrix = []
  7. dp = [[0] * cols for _ in range(rows)]
  8.  
  9. for _ in range(rows):
  10.     matrix.append([int(x) for x in input().split()])
  11.  
  12. dp[0][0] = matrix[0][0]
  13.  
  14. # filling in base row and base col in dp
  15. for col in range(1, cols):
  16.     dp[0][col] = dp[0][col - 1] + matrix[0][col]
  17.  
  18. for row in range(1, rows):
  19.     dp[row][0] = dp[row - 1][0] + matrix[row][0]
  20.  
  21. for row in range(1, rows):
  22.     for col in range(1, cols):
  23.         dp[row][col] = max(dp[row - 1][col], dp[row][col - 1]) + matrix[row][col]
  24.  
  25. row = rows - 1
  26. col = cols - 1
  27. result = deque()
  28. result.appendleft([row, col])
  29.  
  30. while row > 0 and col > 0:
  31.     if dp[row - 1][col] > dp[row][col - 1]:
  32.         row -= 1
  33.     else:
  34.         col -= 1
  35.     result.appendleft([row, col])
  36.  
  37. while row > 0:
  38.     row -= 1
  39.     result.appendleft([row, col])
  40. while col > 0:
  41.     col -= 1
  42.     result.appendleft([row, col])
  43.  
  44. # result.appendleft([0, 0])
  45.  
  46. print(*result)
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement