题解 | #最小三角路径和# 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][];

        // 初始化dp数组，创建并初始化每一行的数组
        for (int i = 0; i < n; i++) {
            dp[i] = new int[cows[i].length];
        }

        // 设置初始值
        dp[0][0] = cows[0][0];

        // 动态规划计算最小路径和
        for (int i = 1; i < n; i++) {
            int m = cows[i].length;
            for (int j = 0; j < m; j++) {
                if (j == 0) {
                    dp[i][j] = dp[i - 1][j] + cows[i][j];
                } else if (j == m - 1) {
                    dp[i][j] = dp[i - 1][j - 1] + cows[i][j];
                } else {
                    dp[i][j] = Math.min(dp[i - 1][j - 1], dp[i - 1][j]) + cows[i][j];
                }
            }
        }

        // 找出最小路径和
        int ans = Integer.MAX_VALUE;
        for (int num : dp[n - 1]) {
            ans = Math.min(ans, num);
        }

        return ans;
    }
}

编程语言是Java。

该题考察的知识点包括：

• 动态规划：通过构建一个二维数组来保存中间状态，以解决更大规模的问题。在这个问题中，使用动态规划来计算三角形矩阵中从顶部到底部的最小路径和。
• 数组操作：创建二维数组，根据条件填充数组元素。

代码的简短文字解释：通过动态规划的思想，创建一个与输入矩阵相同大小的二维数组，逐行计算每个位置的最小路径和，考虑可以向下或向下左方移动。最后，在计算完成后，从最后一行中找出最小的路径和作为结果返回。