# Leetcode [No. 931] Minimum Falling Path Sum

## 題目

2024/1/19 Daily Challenge

## 思路
+ 這個解法是使用bottom up去往上疊，每一格紀錄現在的minimum path sum
+ 因為做bottom up要從最下面那一層開始，每一次都要檢查下面三個哪一個值最小，再把他加到matrix裡面
+ Line11 會直接讓minValue=[i+1][j]的原因是因為值要i+1<matrix.size()時，就一定可以access下面那格，其餘都要做檢查。

class Solution {
public:
    int minFallingPathSum(vector<vector<int>>& matrix) {
        // use a bottom up to record the dp_table
        for(int i = matrix.size()-1; i >= 0; i--)
        {
            for(int j = 0 ; j < matrix[i].size(); j++)
            {
                if(i+1 < matrix.size())
                {
                    int minValue2Add = matrix[i+1][j];
                    if(j-1 >= 0)
                    {
                        minValue2Add = min(minValue2Add, matrix[i+1][j-1]);
                    }
                    if(j+1 < matrix.size())
                    {
                        minValue2Add = min(minValue2Add, matrix[i+1][j+1]);
                    }
                    matrix[i][j] = matrix[i][j] + minValue2Add;
                }
                // cout << dp[i][j] << "\t";
            }
            // cout << endl;
        }
        auto minElement = std::min_element(matrix[0].begin(), matrix[0].end());

        return *minElement;
    }
};

### 解法分析
+ time complexity: O(n^2)
+ space complexity: O(1)

### 執行結果