ภาพรวมปัญหา
มีเมทริกซ์ m×n เต็มจำนวนเต็มบวก หาเส้นทางจากมุมซ้ายบนไปมุมขวาล่าง ที่ให้ผลรวมน้อยที่สุด เคลื่อนที่ได้เฉพาะลงหรือขวา
ตัวอย่าง
| 1 | 3 | 1 |
| 1 | 5 | 1 |
| 4 | 2 | 1 |
Output: 7 (เส้นทาง: 1→3→1→1→1)
อัลกอริทึม (Dynamic Programming - Bottom-up)
- คำนวณ suffix sum ของแถวสุดท้าย (ขวาไปซ้าย)
- คำนวณ suffix sum ของคอลัมน์สุดท้าย (ล่างขึ้นบน)
- เติมตาราง DP จากขวาล่างไปซ้ายบน: dp[i][j] = grid[i][j] + min(dp[i][j+1], dp[i+1][j])
- คำตอบอยู่ที่ dp[0][0]
ตัวอย่างโค้ด (Python)
class Solution(object):
def minPathSum(self, grid):
row = len(grid)-1
column = len(grid[0])-1
i = row-1
j = column-1
while j >= 0:
grid[row][j] += grid[row][j+1]
j -= 1
while i >= 0:
grid[i][column] += grid[i+1][column]
i -= 1
j = column-1
i = row-1
while i >= 0:
while j >= 0:
grid[i][j] += min(grid[i][j+1], grid[i+1][j])
j -= 1
j = column-1
i -= 1
return grid[0][0]
Input / Output
Input: [[1,3,1],[1,5,1],[4,2,1]] Output: 7
