package leetcode.array;

import java.util.List;

/**

* @ClassName Triangle

* @Description 三角形最小路径和 https://leetcode-cn.com/problems/triangle/

* @Author changxuan

* @Date 2020/11/7 下午6:58

**/

public class Triangle {

public int minimumTotal(List<List<Integer>> triangle) {

int n = triangle.size();

// dp[i][j] 表示从点 (i, j) 到底边的最小路径和。

int[][] dp = new int[n + 1][n + 1];

// 从三角形的最后一行开始递推。

for (int i = n - 1; i >= 0; i--) {

for (int j = 0; j <= i; j++) {

dp[i][j] = Math.min(dp[i + 1][j], dp[i + 1][j + 1]) + triangle.get(i).get(j);

}

}

return dp[0][0];

}

}