120. Triangle

1.問題

2.想法

• 提問

  • 確認題意: binary tree的類型, 若非perfect tree, 則無法確定left或right一定存在

• function header, parameter

• test input

• 觀察

  • 第一個邊有一個成員, 第二個邊有兩個成員, 第三個邊有三個成員, 這是一個正三角形

• 說明想法

  • 動態規劃, 跟機器人的路線可能性很像, 不同的只是改成了三角形, 左右兩邊 (正確來說是對角線與row 0)的規則是matrix[j][i] += matrix[j - 1][i], 而中心部分的來源有兩個, 取最小值

  • 切記matrix的縱座標為row (y), 橫坐標為column(x), 表示法為matrix[r][c]

• 測試計算複雜度

3.程式碼

class Solution {
public:
    int minimumTotal(vector<vector<int>>& triangle) {
        if (triangle.size() == 0) {
            return 0;
        }
        
        int n = triangle.size();
        for (int r = 1; r < n; r++) {
            //對角線
            triangle[r][0] += triangle[r - 1][0]; 
            triangle[r][r] += triangle[r - 1][r - 1];
            
            //中間
            for (int c = 1; c < triangle[r].size() - 1; c++) {
                triangle[r][c] = triangle[r][c] + min(triangle[r - 1][c - 1], triangle[r - 1][c]);
            }
        }
        
        int minVal = INT_MAX;
        
        for (int c = 0; c < triangle[n - 1].size(); c++) {
            minVal = min(minVal, triangle[n - 1][c]);
        }
        
        return minVal;
    }
};