题目描述

给定一个三角形，找到从上到下的最小路径和，在每一步可以移动到下一行的相邻数字。

Bonus: 只使用$O(n)$额外空间，其中n是三角形的总行数

样例

输入
[
     [2],
    [3,4],
   [6,5,7],
  [4,1,8,3]
]

输出11 (2 + 3 + 5 + 1 = 11).

算法1

动态规划 时间$O(n^2)$ 空间$O(1)$

点$(i,j)$的下一行的相邻数字是$(i+1,j)$和$(i+1,j+1)$。

$f(i,j)$表示从下往上走到位置$(i,j)$时的最小路径和，计算方式/状态转移方程是

$ f(i,j) = (i,j) + min(f(i+1,j),f(i+1,j+1)) $

复杂度分析：

直接把$f(i,j)$存在位置(i,j)处，不使用额外空间，因此空间复杂度为$O(1)$。

两层for loop，第一次竖着遍历，第二次横着遍历，时间复杂度为$O(n^2)$。

样例：

输入
[
     [2],
    [3,4],
   [6,5,7],
  [4,1,8,3]
]

更新后
[
     [11],
    [9,10,
   [7,6,10],
  [4,1,8,3]
]

C++ 代码

class Solution {
public:
    int minimumTotal(vector<vector<int>>& triangle) {
        for (int i = triangle.size()-2 ; i>=0 ; --i){ //从倒数第二行开始往上
            for (int j = 0 ; j < i+1; ++j){ 
                triangle[i][j] += min(triangle[i+1][j], triangle[i+1][j+1]) ;
            }
        }
        return triangle[0][0];
    }
};