ผลรวมเส้นทางน้อยที่สุด (Minimum Path Sum) ใน Python

โจทย์: กำหนดเมทริกซ์ m×n หาเส้นทางจากมุมซ้ายบนไปขวาล่าง (เดินขวาหรือลงได้อย่างเดียว) ที่มีผลรวมน้อยที่สุด

ตัวอย่าง

Matrix:

1 3 1
1 5 1
4 2 1

อัลกอริทึม: Dynamic Programming (Bottom-up)

1. คำนวณ last row (เดินขวาเท่านั้น) และ last column (เดินลงเท่านั้น)
2. เติมค่าย้อนกลับ: dp[i][j] = grid[i][j] + min(dp[i+1][j], dp[i][j+1])
3. คำตอบอยู่ที่ dp[0][0]

ตัวอย่างโค้ด Python (In-place)

class Solution(object):
    def minPathSum(self, grid):
        if not grid:
            return 0
        
        rows, cols = len(grid), len(grid[0])
        
        # Last row: สะสมไปขวา
        for j in range(cols - 2, -1, -1):
            grid[rows-1][j] += grid[rows-1][j+1]
        
        # Last column: สะสมไปลง
        for i in range(rows - 2, -1, -1):
            grid[i][cols-1] += grid[i+1][cols-1]
        
        # เติมส่วนกลาง
        for i in range(rows - 2, -1, -1):
            for j in range(cols - 2, -1, -1):
                grid[i][j] += min(grid[i+1][j], grid[i][j+1])
        
        return grid[0][0]

# ทดสอบ
ob = Solution()
print(ob.minPathSum([[1,3,1],[1,5,1],[4,2,1]]))  # Output: 7

ตัวอย่าง Input/Output

Input: [[1,3,1],[1,5,1],[4,2,1]]
Output: 7

ความซับซ้อน: Time O(m×n), Space O(1) extra (แก้ไข in-place)