LC 120. Triangle

https://leetcode.com/problems/triangle/description/?envType=study-plan-v2&envId=top-interview-150

class Solution {
public:
    int minimumTotal(vector<vector<int>>& triangle) {
        int m = triangle.size(), n = triangle.back().size();
        vector<vector<int>> f(m, vector<int>(n, INT_MAX));
        f[0][0] = triangle[0][0];
        for (int i = 1; i < m; i++) {
            for (int j = 0; j <= i; j++) {
                f[i][j] = min(j - 1 >= 0 ? f[i - 1][j - 1] : INT_MAX, f[i - 1][j]) + triangle[i][j];
            }
        }
        int ans = INT_MAX;
        for (auto &x: f.back()) ans = min(ans, x);
        return ans;
    }
};

在做 DP 類型的題目時，很重要的就是清楚的知道你的轉移方程，這個轉移方程沒有一定，也就是相同的題目每個人寫出的轉移方程會不同，像是這題你大致上有兩種轉移方程的表示。

第一種:
f[i][j] = min(f[i - 1][j - 1], f[i - 1][j])

第二種:
f[i + 1][j] = min(f[i + 1][j], f[i][j])
f[i + 1][j + 1] = min(f[i + 1][j + 1], f[i][j])

這兩種轉移方程的差異在你更新的角度，如果你的更新的角度是上層更新下層，那你的轉移方程可能會是第二種，如果反過來是下層去找上層，那你的轉移方程會是第一種。

總之雖然轉移方程不同，但是表達的意思是相同的，找一個自己喜歡的就可以了。