题解 | 三角形最小路径和

import java.util.*;


public class Solution {
    
    // 每一步只能移动到下一行的相邻节点上，相邻节点指下行种下标与之相同或下标加一的两个节点
    public int minTrace (int[][] triangle) {
        // write code here
        if (triangle.length == 1) {
            return triangle[0][0];
        }
        int n = triangle.length;
        // 二维dp，算出每一个位置的最小路径和
	  	// 二维dp是用于存储每个位置上的最小路径和，之后通过比较各个最小路径，来确定最小的那个
        int[][] dp = new int[n][n];
        dp[0][0] = triangle[0][0];
        for (int i = 1; i < triangle.length; i++) {
            for(int j = 0; j <= i; j++){
                // j == 0 和 j == i都是边界条件
                if(j == 0){
                    dp[i][0] = dp[i - 1][0] + triangle[i][0];
                }else if(j == i){
                    dp[i][j] = dp[i - 1][j - 1] + triangle[i][j];
                }else{
                    dp[i][j] = Math.min(dp[i - 1][j - 1], dp[i - 1][j]) + triangle[i][j];
                }
            }
        }
        int res = dp[n - 1][0];
        for(int i = 1; i < n; i++){
            res = Math.min(res, dp[n - 1][i]);
        }


        return res;
    }
}