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

知识点：动态规划

对于每一行来说，我们最小的路径和取决于上一行的元素和大小，我们对当前行的每一个元素进行判断，取其上一行的两个相邻元素和中最小的那个作为经过当前元素的最小路径和，每一层都重复以上判断，最终我们遍历最后一行列的元素，得到最小的路径和。部分测试用例有些问题，并不符合题目所说的三角形排列，故我们需要注意遍历每一行元素时，要根据每一行实际的长度进行遍历操作。

Java题解如下

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param cows int整型二维数组 
     * @return int整型
     */
    public int minimumTotal (int[][] cows) {
        // write code here
        int n = cows.length;
        int[][] dp = new int[n][n];
        dp[0][0] = cows[0][0];
        for(int i = 1; i < n; i++) {
            dp[i][0] = dp[i - 1][0] + cows[i][0];
            dp[i][cows[i].length - 1] = dp[i - 1][i - 1] + cows[i][cows[i].length - 1];
            for(int j = 1; j < cows[i].length - 1; j++) {
                dp[i][j] = cows[i][j] + Math.min(dp[i - 1][j], dp[i - 1][j - 1]);
            }
        }
        int min = Integer.MAX_VALUE;
        for(int i = 0; i < cows[n - 1].length; i++) {
            min = Math.min(min, dp[n - 1][i]);
        }
        return min;
    }
}