leetcode_120. 三角形最小路径和

字节跳动 动态规划
给定一个三角形，找出自顶向下的最小路径和。每一步只能移动到下一行中相邻的结点上。

相邻的结点 在这里指的是 下标 与 上一层结点下标 相同或者等于 上一层结点下标 + 1 的两个结点。

[
     [2],
    [3,4],
   [6,5,7],
  [4,1,8,3]
]                            自顶向下的最小路径和为 11（即，2 + 3 + 5 + 1 = 11）

动态规划

/
求最小路径和：sub(2) = min(sub(3), sub(4)) + [2]
DP方程：dp[i][j] = min(dp[i+1][j], dp[i+1][j+1]) + array[i][j]
从下往上算，因为从下往上能确定下面选择哪一个，而从上往下，不能确定选择哪一个是最小的。
/

class Solution {
public:
    int minimumTotal(vector<vector<int>>& triangle) {
        int n = triangle.size();
        vector<vector<int>> dp = triangle;
        for (int i = n - 2; i >= 0; i--) {
            for (int j = 0; j < triangle[i].size(); j++) {
                dp[i][j] += min(dp[i+1][j], dp[i+1][j+1]);
            }
        }
        return dp[0][0];
    }
};
--
--空间优化，把状态数组优化成一维
--在上述代码中，我们定义了一个 NN 行 NN 列 的 dpdp 数组（NN 是三角形的行数）。
--但是在实际递推中我们发现，计算 dp[i][j]dp[i][j] 时，只用到了下一行的 dp[i + 1][j]dp[i+1][j] 和 dp[i + 1][j + 1]dp[i+1][j+1]。
--因此 dpdp 数组不需要定义 NN 行，只要定义 1 行就阔以啦。
--
class Solution {
public:
    int minimumTotal(vector<vector<int>>& triangle) {
        int n = triangle.size();
        vector<int> dp(triangle[n-1].size(), 0);
        for (int i = n - 1; i >= 0; i--) {  //从最后一层开始算
            for (int j = 0; j < triangle[i].size(); j++) {
                if(i == n - 1) {
                    dp[j] = triangle[i][j]; //初始化最后一层。  
                }else {
                    dp[j] = min(dp[j], dp[j+1]) + triangle[i][j];
                }
            }
        }
        return dp[0];
    }
};