题目
给定一个三角形 triangle ,找出自顶向下的最小路径和。
每一步只能移动到下一行中相邻的结点上。相邻的结点 在这里指的是 下标 与 上一层结点下标 相同或者等于 上一层结点下标 + 1 的两个结点。也就是说,如果正位于当前行的下标 i ,那么下一步可以移动到下一行的下标 i 或 i + 1 。
代码
class Solution {
public int minimumTotal(List<List<Integer>> triangle) {
int row=triangle.size();
int[][] result=new int[row+1][row+1];
for(int i=row-1;i>=0;i--)
{
for(int j=0;j<=i;j++)
{
if(i==row-1)
{
result[i][j]=triangle.get(i).get(j);
}else
{
result[i][j]=Math.min(result[i+1][j],result[i+1][j+1])+triangle.get(i).get(j);
}
}
}
return result[0][0];
}
}