题解 | 三角形最小路径和

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *dp非常好！你想通过 在 dp 表中增加一行 0 和一列 0，来简化边界判断和状态转移逻辑，并且希望：

✅ 让 dp[i][j] 表示从顶部到第 i 行、第 j 列的最小路径和

✅ 并且使用 dp[0][0] 或者额外的一行/列来处理边界情况

🎯 目标：
让 dp[n][j] 表示第 n 行所有位置的最小路径和（即最后一行），并避免写复杂的边界条件。
在dp表加一行0再加一列0，使dp[n][j]直接表示n行的最小值，不用dp[n - 1][j]
     * @param triangle int整型二维数组 
     * @return int整型
     */
    public int minTrace (int[][] triangle) {
       
     if(triangle.length==1){
        return triangle[0][0];
     }

        int n=triangle.length;
        //n行n列
        int dp[][]=new int[n+1][n+1];
  // 初始化第一行
        dp[1][1] =triangle[0][0] ;
        for(int i=2;i<=n;i++){
            for(int k=1;k<=i;k++){
                if(k==1){
                     // 最左边只能从上一行的0位置下来
                    dp[i][k] = dp[i - 1][k] + triangle[i-1][k-1];
                }else if(k==i){
                // 最右边只能从上一行的j-1位置下来
                    dp[i][k] = dp[i - 1][k - 1] + triangle[i-1][k-1];
                }else{
                dp[i][k]=Math.min(dp[i-1][k],dp[i-1][k-1])+triangle[i-1][k-1];}
            }
        }
        int minnum=Integer.MAX_VALUE;

        for(int k=1;k<=n;k++){
        if(dp[n][k]<minnum){
            minnum=dp[n][k];
        }
    }
    return minnum;
}
}