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

import java.util.*;


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

}

本题考察的知识点是动态规划，所用编程语言是java.我相信很多人对于此题的动态规划方程的建立并不难，主要我想说一下此题

的易错点，边界情况和每行元素个数并不等于行数，我提一点很多人可能误以为每行元素个数等于行数，可能最后一个测试示例并不会通过，可能会以为题目答案错了，我想提醒大家的是最后一个示例每行元素个数不等于行数