Giả sử chúng ta có một tam giác. Ta phải tìm tổng đường đi nhỏ nhất từ đỉnh đến đáy. Mỗi bước có thể di chuyển đến các số liền kề trên hàng dưới.
Ví dụ, tam giác:
[ [2], [3,4], [6,5,7], [4,1,8,3] ]
Tổng đường đi nhỏ nhất từ đỉnh đến đáy là 11 (2 + 3 + 5 + 1 = 11).
Các bước:
- Tạo bảng DP cho quy hoạch động.
- n := kích thước tam giác
- for i := n – 2 down to 0
- for j := 0 to i
- dp[j] := triangle[i, j] + min(dp[j], dp[j + 1])
- for j := 0 to i
- return dp[0]
Hãy xem triển khai sau:
Ví dụ
class Solution { public: void printVector(vector <int>& v){ for(int i = 0; i < v.size(); i++)cout << v[i] << " "; cout << endl; } int minimumTotal(vector<vector<int>>& triangle) { vector <int> dp(triangle.back()); int n = triangle.size(); for(int i = n - 2; i >= 0; i--){ for(int j = 0; j <= i; j++){ dp[j] = triangle[i][j] + min(dp[j], dp[j + 1]); } // printVector(dp); } return dp[0]; } };Input
[[2],[3,4],[6,5,7],[4,1,8,3]]
Output
11