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

题目考察的知识点

考察动态规划的应用

题目解答方法的文字分析

构建dp数组，dp[i][j]表示到达位置cows[i][j]的最小路径和。对于第一列的元素根据题意只能由正上方得到，对角线的元素只能由上一列最右侧得到。对于中间的值则是根据同一行前一位置以及上一行同一列的位置得到，故有24行的转移方程。最后遍历完所有的位置后取dp矩阵最后一行的最大值即可。

本题解析所用的编程语言

使用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]; //第一列只能由上一列加过来
        }
        for (int i = 1; i < n; i++) {
            for (int j = 1; j < cows[i].length && j < i; j++) { //从第一列开始遍历
                dp[i][j] = Math.min(dp[i - 1][j], dp[i - 1][j - 1]) + cows[i][j];
            }
            dp[i][i] = dp[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(dp[n - 1][i], weight);
        }
        return weight;
    }
}