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

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param triangle int整型二维数组 
     * @return int整型
     */
    /**********************************************************************************/
    // 暴力破解法、深度优先遍历(算法超时)
    /*
    public int minTrace (int[][] triangle) {
        // write code here
        return process(triangle, 0, 0, triangle.length - 1, 0);
    }
    
    public int process(int[][] triangle, int i, int j, int n, int num) {
        
        if (i > n) {
            return num;
        }
        
        num += triangle[i][j];
        if (j == n) {
            return num;
        }
        int d = process(triangle, i + 1, j, n, num);
        int dr = process(triangle, i + 1, j + 1, n, num);
        return Math.min(d, dr);
    }
    */
    
    /**********************************************************************************/
    // 动态规划
    public int minTrace (int[][] triangle) {
        
        int n = triangle.length;
        // 一些特殊情况的处理
        if (1 == n) {
            return triangle[0][0];
        }
        
        int[][] dp = new int[n][n];
        dp[0][0] = triangle[0][0];
        int res = Integer.MAX_VALUE;
        for (int i = 1; i < n; i++) { // 行
            for (int j = 0; j <= i; j++) { // 列
                if (j == 0) {
                    dp[i][j] = dp[i-1][j] + triangle[i][j];
                }
                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];
                }
                if (i == n - 1) {
                    res = Math.min(res, dp[i][j]);
                }
            }
        }
        return res;
    }
}