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

大家好，我是开车的阿Q，自动驾驶的时代已经到来，没时间解释了，快和阿Q一起上车。作为自动驾驶系统工程师，必须要有最好的C++基础，让我们来一起刷题吧。

题目考察的知识点

这道题目考察的是动态规划算法和数组的处理。

题目解答方法的文字分析

首先，我们需要定义一个二维的 DP 数组 dp，其中 dp[i][j] 表示从三角形顶部到第 i 行第 j 列位置的最小体重总和。

接下来，我们来考虑动态规划的转移方程。我们可以根据上一行的结果来计算当前行的结果。对于当前行的第 j 列，可以从上一行的第 j 列或者第 j-1 列移动过来，取两者中的较小值，并加上当前位置的体重值，即 dp[i][j] = min(dp[i-1][j], dp[i-1][j-1]) + cows[i][j]。

最后，我们需要找到最后一行的最小值，即为从三角形顶部到三角形底部的挤奶路径上所有奶牛的体重总和的最小值。

本题解析所用的编程语言

C++

完整且正确的编程代码

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param cows int整型vector<vector<>> 
     * @return int整型
     */
    int minimumTotal(vector<vector<int>>& cows) {
        int n = cows.size();

        // 定义二维 DP 数组
        vector<vector<int>> dp(n, vector<int>(n, 0));

        // 初始化三角形顶部的体重值
        dp[0][0] = cows[0][0];

        // 动态规划递推
        for (int i = 1; i < n; ++i) {
            for (int j = 0; j <= i; ++j) {
                // 计算当前位置的最小体重总和
                if (j == 0) {
                    dp[i][j] = dp[i - 1][j] + cows[i][j];
                } else if (j == i) {
                    dp[i][j] = dp[i - 1][j - 1] + cows[i][j];
                } else {
                    dp[i][j] = min(dp[i - 1][j], dp[i - 1][j - 1]) + cows[i][j];
                }
            }
        }

        // 找到最后一行的最小值，即为挤奶路径上所有奶牛的体重总和的最小值
        int result = dp[n - 1][0];
        for (int j = 1; j < n; ++j) {
            result = min(result, dp[n - 1][j]);
        }

        return result;
    }
};

您的关注、点赞、收藏就是我创作的动力，三连支持阿Q！