面试经典算法题78-三角形最小路径和

LeetCode.120

问题描述

给定一个三角形 triangle ，找出自顶向下的最小路径和。

每一步只能移动到下一行中相邻的结点上。相邻的结点 在这里指的是 下标 与 上一层结点下标 相同或者等于 上一层结点下标 + 1 的两个结点。也就是说，如果正位于当前行的下标 i ，那么下一步可以移动到下一行的下标 i 或 i + 1 。

示例 1：

输入：triangle = [[2],[3,4],[6,5,7],[4,1,8,3]]
输出：11
解释：如下面简图所示：
   2
  3 4
 6 5 7
4 1 8 3
自顶向下的最小路径和为 11（即，2 + 3 + 5 + 1 = 11）。

示例 2：

输入：triangle = [[-10]]
输出：-10

思路

1. 状态定义：使用一个数组 dp，其中 dp[i] 表示从当前行到达底部的最小路径和。
2. 状态转移方程：从底部开始向上更新 dp 数组。对于每一个位置 i，更新公式为：dp[i] = min(dp[i], dp[i + 1]) + triangle[row][i]。
3. 初始状态：dp 数组初始化为三角形最后一行的值。
4. 结果：最终结果存储在 dp[0] 中，即从顶到底的最小路径和。

参考代码

C++

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int minimumTotal(vector<vector<int>>& triangle) {
    if (triangle.empty()) return 0;

    // 初始化 dp 数组为三角形最后一行的值
    vector<int> dp = triangle.back();

    // 从倒数第二行开始向上更新 dp 数组
    for (int row = triangle.size() - 2; row >= 0; --row) {
        for (int i = 0; i <= row; ++i) {
            dp[i] = min(dp[i], dp[i + 1]) + triangle[row][i];
        }
    }

    // dp[0] 保存了从顶到底的最小路径和
    return dp[0];
}

int main() {
    vector<vector<int>> triangle1 = {
        {2},
        {3, 4},
        {6, 5, 7},
        {4, 1, 8, 3}
    };
    cout << "输入: [[2],[3,4],[6,5,7],[4,1,8,3]]" << endl;
    cout << "输出: " << minimumTotal(triangle1) << endl; // 输出: 11

    vector<vector<int>> triangle2 = {
        {-10}
    };
    cout << "输入: [[-10]]" << endl;
    cout << "输出: " << minimumTotal(triangle2) << endl; // 输出: -10

    return 0;
}

Java

import java.util.List;
import java.util.Arrays;

public class Triangle {

    public static int minimumTotal(List<List<Integer>> triangle) {
        if (triangle == null || triangle.size() == 0) {
            return 0;
        }

        // 初始化 dp 数组为三角形最后一行的值
        int[] dp = new int[triangle.size()];
        for (int i = 0; i < triangle.get(triangle.size() - 1).size(); i++) {
            dp[i] = triangle.get(triangle.size() - 1).get(i);
        }

        // 从倒数第二行开始向上更新 dp 数组
        for (int row = triangle.size() - 2; row >= 0; row--) {
            for (int i = 0; i <= row; i++) {
                dp[i] = Math.min(dp[i], dp[i + 1]) + triangle.get(row).get(i);
            }
        }

        // dp[0] 保存了从顶到底的最小路径和
        return dp[0];
    }

    public static void main(String[] args) {
        List<List<Integer>> triangle1 = Arrays.asList(
            Arrays.asList(2),
            Arrays.asList(3, 4),
            Arrays.asList(6, 5, 7),
            Arrays.asList(4, 1, 8, 3)
        );
        System.out.println("输入: [[2],[3,4],[6,5,7],[4,1,8,3]]");
        System.out.println("输出: " + minimumTotal(triangle1));  // 输出: 11

        List<List<Integer>> triangle2 = Arrays.asList(
            Arrays.asList(-10)
        );
        System.out.println("输入: [[-10]]");
        System.out.println("输出: " + minimumTotal(triangle2));  // 输出: -10
    }
}

Python

from typing import List

def minimumTotal(triangle: List[List[int]]) -> int:
    if not triangle:
        return 0

    # 初始化 dp 数组为三角形最后一行的值
    dp = triangle[-1]

    # 从倒数第二行开始向上更新 dp 数组
    for row in range(len(triangle) - 2, -1, -1):
        for i in range(row + 1):
            dp[i] = min(dp[i], dp[i + 1]) + triangle[row][i]

    # dp[0] 保存了从顶到底的最小路径和
    return dp[0]

# 主方法：用于测试
if __name__ == "__main__":
    triangle1 = [
        [2],
        [3, 4],
        [6, 5, 7],
        [4, 1, 8, 3]
    ]
    print("输入: [[2],[3,4],[6,5,7],[4,1,8,3]]")
    print("输出:", minimumTotal(triangle1))  # 输出: 11

    triangle2 = [
        [-10]
    ]
    print("输入: [[-10]]")
    print("输出:", minimumTotal(triangle2))  # 输出: -10