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

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param cows int整型二维数组
     * @return int整型
     */
    public static int minimumTotal(int[][] cows) {
        // 创建一个二维数组来保存路径和
        int[][] dp = new int[cows.length][cows.length];

        // 初始化第一行
        dp[0][0] = cows[0][0];

        // 逐行计算最小路径和
        for (int i = 1; i < cows.length; i++) {
            dp[i][0] = dp[i - 1][0] + cows[i][0]; // 两端位置只有一种选择

            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 minWeight = Integer.MAX_VALUE;
        for (int weight : dp[cows.length - 1]) {
            minWeight = Math.min(minWeight, weight);
        }

        return minWeight;
    }
}

该代码使用Java编写。它解决的问题是求解一个三角形数组中从顶部到底部的最小路径和。算法使用了动态规划的思想。

知识点：

• 二维数组的基本操作：创建、访问元素
• 动态规划的思想：通过子问题的最优解来求解原始问题的最优解
• 三角形数组的特点：每一行的列数逐渐增加，且每个位置只能通过上一行相邻的位置到达

代码解释大纲：

1. 创建一个二维数组dp来保存路径和。该数组的行数和列数都与输入的cows数组的行数相同。
2. 初始化dp数组的第一行，即dp[0][0] = cows[0][0]。
3. 逐行计算最小路径和：对于每一行的两端位置，只有一种选择。因此，更新dp[i][0] = dp[i - 1][0] + cows[i][0]。对于中间位置（除去两端），计算路径和时要考虑两条路径，选择其中较小的一条。更新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]。
4. 在最后一行中找到最小路径和，遍历最后一行的元素，更新minWeight = Math.min(minWeight, weight)。
5. 返回最小路径和minWeight。