#yyds干货盘点# LeetCode程序员面试金典：三角形最小路径和

题目：

给定三角形 triangle ，找出自上而下的最小路径和。

每一步只能移动到下一行中相邻的结点。相邻的结点 这里指的是 下标 与 下标上层结点 相同或等于 下标上层结点 + 1 两个结点。也就是说，如果位于当前的下标点 i ，然后下一步可以移动到下一行下标 i 或 i + 1 。

示例 1：

输入：triangle = [2]，[3，4]，[6，5，7]，[4，1，8，3]

输出：11

说明:如下图所示:

2

3 4

6 5 7

4 1 8 3

自顶向下的最小路径为11(即2+3+5+1)= 11）。

示例 2：

输入：triangle = [[-10]]

输出：-10

代码实现：

class Solution {    public int minimumTotal(List<List<Integer>> triangle) {        int n = triangle.size();        int[][] f = new int[n][n];        f[0][0] = triangle.get(0).get(0);        for (int i = 1; i < n; ++i) {            f[i][0] = f[i - 1][0] + triangle.get(i).get(0);            for (int j = 1; j < i; ++j) {                f[i][j] = Math.min(f[i - 1][j - 1], f[i - 1][j]) + triangle.get(i).get(j);            }            f[i][i] = f[i - 1][i - 1] + triangle.get(i).get(i);        }        int minTotal = f[n - 1][0];        for (int i = 1; i < n; ++i) {            minTotal = Math.min(minTotal, f[n - 1][i]);        }        return minTotal;    }}