Tam giác trong C++

Cho tam giác số, tìm tổng đường đi nhỏ nhất từ đỉnh đến đáy. Mỗi bước chỉ được đi sang số liền kề hàng dưới.

Ví dụ: [[2],[3,4],[6,5,7],[4,1,8,3]] → 11 (2+3+5+1).

Thuật toán giải quyết (DP bottom-up 1 chiều)

1. Khởi tạo dp = hàng cuối cùng của tam giác.
2. Duyệt từ hàng n-2 về 0:
   • Với mỗi j = 0..i: dp[j] = triangle[i][j] + min(dp[j], dp[j+1]).
3. Kết quả = dp[0].

Ví dụ minh họa (C++)

#include <bits/stdc++.h>
using namespace std;

class Solution {
public:
    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]);
            }
        }
        return dp[0];
    }
};

int main() {
    Solution ob;
    vector<vector<int>> v = {{2},{3,4},{6,5,7},{4,1,8,3}};
    cout << ob.minimumTotal(v);
}

Đầu vào

[[2],[3,4],[6,5,7],[4,1,8,3]]

Đầu ra

11