题解 | #三角形最小路径和#动态规划

自下往上的动态规划

定义dp[i][j] : 第i行第j列的元素的最小路径和

状态转移 dp[i][j] = Math.min(dp[i+1][j],dp[i+1][j+1])+nums[i][j]

最后返回dp[0][0]

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param triangle int整型二维数组 
     * @return int整型
     */
    public int minTrace (int[][] triangle) {
        // write code here
        int n = triangle.length;
        //dp[i][j] : 第i行第j列为头往下的最小路径和
        int[][] dp = new int[n][];
        for(int i = 0;i<n;i++){
            dp[i] = new int[i+1];
        }
	  //先初始化最后一行的值
        for(int i = 0;i<n;i++){
            dp[n-1][i] = triangle[n-1][i];
        }
	  //我们从下往上 因为每一个信息都需要他的下面和右下的信息 所以要从下往上
        for(int i = triangle.length-2;i>=0;i--){
            for(int j = 0;j<=i;j++){
			  //状态转移方程
                dp[i][j] = Math.min(dp[i+1][j],dp[i+1][j+1])+triangle[i][j];
            }
        }
        return dp[0][0];
    }
}