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

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param cows int整型二维数组
     * @return int整型
     */
    public 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 i = 1; i < cows.length; 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[cows.length - 1][i], weight);
        }
        return weight;
    }
}

本题知识点分析：

1.动态规划

2.数组遍历

3.数学模拟

本题解题思路分析：

1.本题就是数塔问题

2.dp数组是什么，每一层的总和，从上往下

3.dp数组初始化，dp[0][0] = cows[0][0]; 第一层只有一种选择

4.dp公式 dp[i][j] = Math.min(dp[i - 1][j], dp[i - 1][j - 1]) + cows[i][j]; 上一行的当前列或者是上一行的前一列加上当前cows[i][j]取小的那个

5.

for (int i = cows.length - 1; i >= 0; i--) {
            weight = Math.min(dp[cows.length - 1][i], weight);
        }
// 寻找最后一层最小的总和

6.将总和返回即可

本题使用编程语言: Java