120-三角形最小路径和

LeetCode 120. Triangle

LeetCode-120

Given a triangle array, return the minimum path sum from top to bottom.

For each step, you may move to an adjacent number of the row below. More formally, if you are on index i on the current row, you may move to either index i or index i + 1 on the next row.

Example 1:

Input: triangle = [[2],[3,4],[6,5,7],[4,1,8,3]]
Output: 11
Explanation: The triangle looks like:
   2
  3 4
 6 5 7
4 1 8 3
The minimum path sum from top to bottom is 2 + 3 + 5 + 1 = 11 (underlined above).

method

除了最左边和最右边的元素，中间的元素都可以从左上角和上方过来，所以只要两者之间的较小值进行累加

递推方程：dp[i][j] += min(dp[i-1][j-1], dp[i-1][j])

int minimumTotal(vector<vector<int>>& nums) {
    int m = nums.size();
    for (int i = 1; i < m; i++) {
        for (int j = 0; j <= i; j++) {
            if (j == 0) nums[i][j] += nums[i - 1][j];   // 最左边
            else if (j == i) nums[i][j] += nums[i - 1][j - 1];  // 最右边
            else nums[i][j] += min(nums[i - 1][j - 1], nums[i - 1][j]); // 中间
        }
    }
    int res = INT_MAX;
    for (int j = 0; j < m; j++) {
        res = min(res, nums[m - 1][j]); // 找出最后一行的最小值
    }
    return res;
}