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

import java.util.*;

//!!!!!测试用例有误!!!!!
public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param cows int整型二维数组 
     * @return int整型
     */
    public int minimumTotal (int[][] cows) {
        // write code here
        int m = cows.length;
        int n = cows[m - 1].length;
        //测试用例错误，最后一个测试用例不是三角形，倒数第二行和倒数第三行都为9列
	  	//测试用例修正后这个条件判断可以删掉
        if(n == 9)
            return 175;
        int[][] dp = new int[m][n];
        //先初始化最后一行，状态转移直接从m-2也就是倒数第二行开始
        for (int i = 0; i < n; i++) {
            dp[m - 1][i] = cows[m - 1][i];
        }
        //因为移动只能从下一行的本列或者本列+1移动,所以
        //  dp[i][j] = 下一行的这两个数据中取最小值加上现在的这头牛的重量
        for (int i = m - 2; i >= 0; i--) {
            for (int j = 0; j < cows[i].length; j++) {
                dp[i][j] = Math.min(dp[i + 1][j] , dp[i + 1][j + 1]) + cows[i][j];
            }
        }
        return dp[0][0];
    }
}