Đề bài
Cho cấu trúc tam giác của các số, tìm tổng đường đi nhỏ nhất từ đỉnh đến đáy. Mỗi bước có thể di chuyển đến số liền kề trên hàng dưới.
Ví dụ
Nếu đầu vào là:
5 7 3 8 1 2 9 6 4 5
Thì tổng nhỏ nhất là 13 như sau:
5 + 3 + 1 + 4
Thuật toán
- Sử dụng kỹ thuật ghi nhớ (memorization) của quy hoạch động
- Tạo mảng 1-D để ghi nhớ
- Với mỗi hàng K sử dụng công thức:
memorization[i] = min( memorization[i], memorization[i+1]) + A[k][i];
Ví dụ mã nguồn
#include <bits/stdc++.h> using namespace std; int getMinSum(vector<vector<int>> &arr) { int memorization[arr.size()]; int n = arr.size() - 1; for (int i = 0; i < arr[n].size(); ++i) { memorization[i] = arr[n][i]; } for (int i = arr.size() - 2; i >= 0; --i) { for (int j = 0; j < arr[i + 1].size() - 1; ++j) { memorization[j] = arr[i][j] + min(memorization[j], memorization[j + 1]); } } return memorization[0]; } int main() { vector<vector<int>> arr = { {5}, {7, 3}, {8, 1, 2}, {9, 6, 4, 5}, }; cout << "Minimum sum path = " << getMinSum(arr) << endl; return 0; } Khi biên dịch và chạy chương trình trên. Nó tạo ra đầu ra sau:
Kết quả
Minimum sum path = 13