Giả sử chúng ta có một tam giác. Chúng ta phải tìm tổng đường đi tối thiểu từ trên xuống dưới. Trong mỗi bước, chúng ta có thể chuyển đến các số liền kề trên hàng bên dưới.
Ví dụ:nếu tam giác sau giống như
[ [2], [3,4], [6,5,7], [4,1,8,3] ]
Tổng đường dẫn tối thiểu từ trên xuống dưới là 11 (2 + 3 + 5 + 1 =11).
Hãy để chúng tôi xem các bước
- Tạo một bảng để sử dụng trong cách tiếp cận Lập trình động.
- n:=kích thước của hình tam giác
- for i:=n - 2 xuống 0
- for j:=0 to i
- dp [j]:=tam giác [i, j] + tối thiểu của dp [j] và dp [j + 1]
- for j:=0 to i
- trả về dp [0]
Hãy cùng chúng tôi xem cách triển khai sau đây để hiểu rõ hơn
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];
}
}; Đầu vào
[ [2], [3,4], [6,5,7], [4,1,8,3] ]
Đầu ra
11