三角形最小路径和 图解题解

三角形最小路径和到底在求什么

给一个数字三角形 triangle，从顶上出发，每步只能走到下一行紧挨着的两个数之一——正下方或右下方，走到最底行，求这一路数字之和最小。以 [[2],[3,4],[6,5,7],[4,1,8,3]] 为例，走 2→3→5→1 得 11，是所有走法里最小的，答案就是 11。

为什么不能把每条路径都走一遍

最直接的想法是把每条路径都走一遍比出最小的。但每往下一行都要二选一，n 行三角形有约 2 的 n-1 次方条路径，指数级膨胀、枚举不完。慢在同一个格子被反复经过，往下那段路在无数条路径里一遍遍重算。既然每个格子往下的最优走法固定，算一次存下来复用，这就是动态规划——算过的子问题记下复用、不再重算。

为什么反过来从最底行往上填

不从顶往下算，而是从最底行倒着往上推。定义 dp[j] 为「当前这一行第 j 个格子往下走到底的最小路径和」。最底行的格子已经到底，最小和就是自己。往上一行行覆盖，算上面某格时它下面正铺着刚算完的一行。

好处是每个非底行的格子都规整地有正下方、右下方两条来路。若从顶往下填，每行头尾只有一条来路（贴着斜边），要单独写边界判断；倒着从底往上，这类首尾特判整个消失。

本格加下方两格较小，为什么能压成一行

转移式（由已算好的格子推出当前格子的公式）就一句：dp[j] = triangle[i][j] + min(dp[j], dp[j+1])，本格值加上正下方、右下方里更小的那个。下标别弄反：正下方是 dp[j]、右下方是 dp[j+1]，同一个 j 差一位。

算当前行第 j 格只用到下一行的 dp[j] 和 dp[j+1]，再往下的行用不上了。所以不必存整张二维表，只需一个长度等于行数的一维数组，从底行起每算一行就地覆盖旧值。这种把二维表滚成一行的写法叫滚动数组，空间从 O(n²) 压到 O(n)。

拿这个三角形把每一格亲手填一遍

拿 [[2],[3,4],[6,5,7],[4,1,8,3]] 走一遍。最底行 [4,1,8,3] 各自到底，dp 起始就是 4、1、8、3。往上一行 [6,5,7]：6 的下方是 4 和 1 取 1，记 6+1=7；5 的下方是 1 和 8 取 1，记 5+1=6；7 的下方是 8 和 3 取 3，记 7+3=10。这行 dp 是 7、6、10。

再上一行 [3,4]：3 的下方是 7 和 6 取 6，记 3+6=9；4 的下方是 6 和 10 取 6，记 4+6=10，dp 是 9、10。顶行 [2]：2 的下方是 9 和 10 取 9，记 2+9=11。填到顶格得 11，就是这个三角形的最小路径和。

复杂度是多少，两个下标和答案位置别搞错

三角形约 n²/2 个格子，每格一次取小、一次加法都是常数，时间 O(n²)；一维滚动只留一行，空间 O(n)。

两处最容易出错。一是下标：正下方 dp[j]、右下方 dp[j+1]，写成 dp[j-1] 或取反就顺着错路加。二是答案位置：填完后答案是顶格 dp[0]，它汇总了全部路径，不是最底行里最小的数——底行的值只是各自起点。数带负号也照样成立。

Python

def minimumTotal(triangle):
    dp = triangle[-1][:]            # 最底行
    for i in range(len(triangle)-2, -1, -1):
        for j in range(i+1):
            dp[j] = triangle[i][j] + min(dp[j], dp[j+1])
    return dp[0]

C++

int minimumTotal(vector<vector<int>>& t){
    vector<int> dp = t.back();
    for(int i = t.size()-2; i >= 0; i--)
        for(int j = 0; j <= i; j++)
            dp[j] = t[i][j] + min(dp[j], dp[j+1]);
    return dp[0];
}

Java

int minimumTotal(List<List<Integer>> t){
    int n = t.size();
    int[] dp = new int[n + 1];
    for(int i = n - 1; i >= 0; i--)
        for(int j = 0; j <= i; j++)
            dp[j] = t.get(i).get(j) + Math.min(dp[j], dp[j + 1]);
    return dp[0];
}