30daychalenge (18) || Minimum Path Sum

Given a m x n grid filled with non-negative numbers, find a path from top left to bottom right which minimizes the sum of all numbers along its path.

Note: You can only move either down or right at any point in time.

Example:

Input:
[
  [1,3,1],
  [1,5,1],
  [4,2,1]
]
Output: 7
Explanation: Because the path 1→3→1→1→1 minimizes the sum.

Ban đầu tôi nghĩ đến dùng Dijkstra, nhưng sau một hồi quan sát thì thấy nó rất giống bài Kim tự tháp ngày xưa tôi từng làm, vâng, và tôi sẽ implement nó bằng quy hoạch động.

Đề bài chỉ cho xuất phát từ điểm đầu góc trái, bắt đi đến điểm cuối góc phải, vì thế quy hoạch động càng dễ hơn. Thêm nữa là chỉ được phép đi xuống dưới, hoặc đi sang phải, thế thì nghiệm tại vị trí bất kỳ [i][j] sẽ bằng min điểm xuống dưới đã có nghiệm gần nhất (chính là điểm trên nó) + grid[i][j] hoặc điểm bên phải tương tự.

Suy ra ta có công thức truy hồi: dp[i][j] = min (dp[i-1][j],dp[i][j-1]) + grid[i][j].

Xong rồi nhé. Đây là code trên Java:


Hết rồi, hẹn gặp Leetcode vào ngày mai. Cảm ơn bạn !