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][];
        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。

该题考察的知识点是动态规划。

代码的简短解释如下：

1. 创建一个与输入二维数组大小相匹配的dp数组，用于存储中间结果。
2. 将第一个元素的值直接赋给dp[0][0]，作为初始值。
3. 从第二行开始遍历，逐行计算最小路径和。对于每一行的元素，根据其位置和上一行的元素值，选择路径和更小的路径进行累加得到最小路径和。如果当前元素是行中的第一个元素（最左边），则只能从上一行的相同位置处向下移动到当前位置，路径和为dp[i-1][j] + cows[i][j]。如果当前元素是行中的最后一个元素（最右边），则只能从上一行的前一个位置处向下移动到当前位置，路径和为dp[i-1][j-1] + cows[i][j]。对于其他情况，可以从上一行的前一个位置或相同位置处向下移动到当前位置，取路径和较小的值：Math.min(dp[i-1][j-1], dp[i-1][j]) + cows[i][j]。
4. 在dp数组的最后一行中找到最小值，即为最终的最小路径和。