题目描述

给定一个三角形 triangle，找出自顶向下的最小路径和。每一步只能移动到下一行中相邻的结点上。

例如，给定三角形：

[
     [2],
    [3,4],
   [6,5,7],
  [4,1,8,3]
]

自顶向下的最小路径和为 11（即，2 + 3 + 5 + 1 = 11）。

解题思路

我们可以使用动态规划来解决这个问题。从三角形的底部开始，逐步向上更新每个位置的最小路径和。在到达三角形的顶部时，顶部元素的值就是最小路径和。

PHP 示例代码

function minimumTotal($triangle) {
    $rows = count($triangle);
    if ($rows == 0) return 0;
    
    // 从倒数第二行开始向上计算最小路径和
    for ($i = $rows - 2; $i >= 0; $i--) {
        for ($j = 0; $j <= $i; $j++) {
            // 当前位置的最小路径和等于它自身加上下面相邻两个位置中较小的那个
            $triangle[$i][$j] += min($triangle[$i + 1][$j], $triangle[$i + 1][$j + 1]);
        }
    }
    
    // 三角形的顶部元素即为所求的最小路径和
    return $triangle[0][0];
}

// 示例
$triangle = [
    [2],
    [3,4],
    [6,5,7],
    [4,1,8,3]
];
echo minimumTotal($triangle); // 输出 11

Python 示例代码

def minimumTotal(triangle):
    if not triangle:
        return 0
    
    rows = len(triangle)
    # 从倒数第二行开始向上计算
    for i in range(rows - 2, -1, -1):
        for j in range(i + 1):
            triangle[i][j] += min(triangle[i + 1][j], triangle[i + 1][j + 1])
    
    # 三角形的顶部元素即为所求
    return triangle[0][0]

# 示例
triangle = [
    [2],
    [3,4],
    [6,5,7],
    [4,1,8,3]
]
print(minimumTotal(triangle))  # 输出 11

JavaScript 示例代码

function minimumTotal(triangle) {
    const rows = triangle.length;
    if (rows === 0) return 0;
    
    // 从倒数第二行开始向上计算
    for (let i = rows - 2; i >= 0; i--) {
        for (let j = 0; j <= i; j++) {
            triangle[i][j] += Math.min(triangle[i + 1][j], triangle[i + 1][j + 1]);
        }
    }
    
    // 三角形的顶部元素即为所求
    return triangle[0][0];
}

// 示例
const triangle = [
    [2],
    [3,4],
    [6,5,7],
    [4,1,8,3]
];
console.log(minimumTotal(triangle)); // 输出 11

以上代码示例均实现了自顶向下的三角形最小路径和问题，并使用了动态规划的思想进行优化。在实际面试中，可以根据需要选择合适的编程语言进行实现。