题解 | #三角形最小路径和#

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param triangle int整型二维数组 
     * @return int整型
     */
    public int minTrace (int[][] triangle) {
        // write code here
        //两种实现：从上往下和从下往上
        //从上往下是每到一行，在数组中更新路径为自身值+上一行的可接触值的路径的最小值，
        //这种方法要注意边界条件
        //最后会得到以最后一行的每个点为终点的路径和最小值，从中找出最小的即可。
        //从下往上是每到一行，在数组中更新路径为自身值+下一行的可接触值的路径的最小值，
        //最后dp【0】就是所要的值
        //要想更节省空间，可以不建新数组，在原数组上修改即可。
        //int min = Top2Bot(triangle);
        int min = Bot2Top(triangle);
        return min;
    }
    
    public int Top2Bot(int[][] triangle){
        //从上往下
        int[] dp = new int[triangle.length];
        dp[0] = triangle[0][0];
        for(int i = 1; i < triangle.length; i++){
            for(int j = i; j >=0; j--){
                if(j == i){
                    dp[j] = dp[j-1] + triangle[i][j];
                }else if(j == 0){
                    dp[j] = dp[j] + triangle[i][j];
                }else{
                    dp[j] = Math.min(dp[j-1],dp[j]) + triangle[i][j];
                }
            }
        }
        int min = Integer.MAX_VALUE;
        for(int i = 0; i < dp.length; i++){
            min = Math.min(min,dp[i]);
        }
        return min;
    }
    
    public int Bot2Top(int[][] triangle){
        //从下往上
        int[] dp = Arrays.copyOf(triangle[triangle.length-1], triangle.length);
        for(int i = triangle.length - 2; i >= 0; i--){
            for(int j = 0; j <= i; j++){
                dp[j] = Math.min(dp[j], dp[j+1]) + triangle[i][j];
            }
        }
        
        return dp[0];
    }
}