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

考察的知识点：动态规划；

解答方法分析：

1. 定义一个二维数组 arr，大小与输入的三角形数组 cows 相同，用于存储达每个位置的最小总权重。
2. 初始化 arr[0][0] 为 cows[0][0]，即三角形的顶部元素。
3. 针对三角形的第一列（即 cows[i][0]），从上往下计算到达每个位置的最小总权重，存储在数组 arr[i][0] 中。计算方法为 arr[i][0] = arr[i-1][0] + cows[i][0]。
4. 针对三角形的其他位置，例如 cows[i][j]，从上往下计算到达每个位置的最小总权重，存储在数组 arr[i][j] 中。计算方法为 arr[i][j] = min(arr[i-1][j], arr[i-1][j-1]) + cows[i][j]。选择上方和左上方两个位置的最小值，并加上当前位置的权重 cows[i][j]。
5. 由于每行的元素个数逐渐增加，所以最后一行的最小总权重应该是从上往下所有路径中权重最小的。因此，循环遍历最后一行的所有元素，记录最小值，并返回该值作为最小总权重。

所用编程语言：C++；

完整编程代码：↓

class Solution {
  public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param cows int整型vector<vector<>>
     * @return int整型
     */
    int minimumTotal(vector<vector<int> >& cows) {
        int n = cows.size();
        vector<vector<int>> arr(n, vector<int>(n, 0));
        arr[0][0] = cows[0][0];
        for (int i = 1; i < n; i++) {
            arr[i][0] = arr[i - 1][0] + cows[i][0];
        }
        for (int i = 1; i < n; i++) {
            for (int j = 1; j < i && j < cows[i].size(); j++) {
                arr[i][j] = min(arr[i - 1][j], arr[i - 1][j - 1]) + cows[i][j];
            }
            arr[i][i] = arr[i - 1][i - 1] + cows[i][cows[i].size() - 1];
        }
        int weight = INT_MAX;
        for (int i = 0; i < n; i++) {
            weight = min(arr[n - 1][i], weight);
        }
        return weight;
    }
};