三角形最小路径和

问题陈述

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

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

代码实现

动态规划+自底向上

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution{
    public int minimumTotal(List<List<Integer>> triangle){
        if(triangle==null||triangle.size()==0) return 0;//判空
        
        int[][] dp=new int[triangle.size()+1][triangle.size()+1];//动态规划
        for(int i=triangle.size()-1;i>=0;i--){
            List<Integer> rows=triangle.get(i);
            for(int j=0;j<row.size();j++){
                dp[i][j]=Math.min(dp[i+1][j],dp[i+1][j+1])+rows.get(j);//转移方程
            }
        }
        return dp[0][0];
    }
}