深度解析三角形最小路径和：从递归到空间优化的动态规划实战

2026-02-07 16:14:18 0条评论 3次阅读 0人点赞

在这篇文章中，我们将深入探讨一道经典的算法题目：三角形最小路径和。这不仅是一道常见的面试题，更是理解动态规划思想从递归演进到空间优化的绝佳案例。我们将从最直观的递归解法出发，一步步引导你如何通过记忆化和制表技术优化性能，最终实现极致的空间复杂度优化。无论你是正在准备算法面试，还是希望提升代码性能，这篇文章都将为你提供详实的指导和实战技巧。

问题陈述与分析

首先，让我们明确一下题目要求。给定一个三角形数组，我们的目标是从顶点出发，移动到底边的最短路径。这里有一个关键限制：在移动过程中，如果我们当前位于索引 INLINECODEa7ce2a60，下一步只能移动到下一行的索引 INLINECODE5bd9fa66 或者 i + 1。

直观理解：

你可以把这个三角形想象成一个决策树。每一个节点都是一个路口，你只能向下直走或者向右下走。我们的目标就是在所有可能的路径中，找到权值之和最小的那条。

示例分析：

让我们通过一个具体的例子来梳理逻辑：

    [2]
   [3, 7]
  [8, 5, 6]
 [6, 1, 9, 3]
  • 路径选择： 如果我们从顶部的 2 出发，第一步可以选择 3 或 7。
  • 寻找最优： 如果我们选择 3，下一步可以选择 8 或 5；如果选择 5，再下一步则是 1 或 9。
  • 计算结果：

* 路径 2 -> 3 -> 5 -> 1 的和是 2 + 3 + 5 + 1 = 11。

* 这是最小值，其他路径如 2 -> 7 -> 6 -> 3 的和为 18。

通过这个例子，我们可以看到，问题的关键在于如何避免重复计算那些重叠的子问题。

方法一：朴素递归法

让我们从最简单的思路开始。对于任意一个单元格 INLINECODE78b892e6，我们只需要关心它下方能走的两个位置：INLINECODE7de32830 和 (i+1, j+1)。要得到当前路径的最小和，我们就取这两个位置返回的最小值，再加上当前单元格的值即可。

核心逻辑：

这个问题具有明显的最优子结构性质。从顶部到底部的最小路径和，等于顶部值加上“从第二行开始到底部的最小路径和”。

#### C++ 实现

#include 
#include 
#include  // 用于 std::min
using namespace std;

/**
 * 递归辅助函数：计算从 到达底部的最小路径和
 * @param triangle 三角形数组引用
 * @param i 当前行索引
 * @param j 当前列索引
 * @return 从 返回的最小和
 */
int minSumPathRec(vector<vector>& triangle, int i, int j) {
    // 基本情况：如果超出最后一行，路径结束，返回0
    if (i == triangle.size())
        return 0;

    // 递归步骤：
    // 当前值 + min(正下方最小值, 右下方最小值)
    int down = minSumPathRec(triangle, i + 1, j);
    int diagonal = minSumPathRec(triangle, i + 1, j + 1);
    
    return triangle[i][j] + min(down, diagonal);
}

int minSumPath(vector<vector>& triangle) {
    return minSumPathRec(triangle, 0, 0);
}

int main() {
    vector<vector> triangle = {
        {2},
        {3, 7},
        {8, 5, 6},
        {6, 1, 9, 3}
    };

    cout << "最小路径和: " << minSumPath(triangle) << endl;
    return 0;
}

#### Python 实现

def min_sum_path_rec(triangle, i, j):
    """
    递归求解从 (i, j) 到底部的最小路径和
    """
    # 基本情况：到达底部边界
    if i == len(triangle):
        return 0
    
    # 递归计算下方和右下方的最小值
    down = min_sum_path_rec(triangle, i + 1, j)
    diagonal = min_sum_path_rec(triangle, i + 1, j + 1)
    
    return triangle[i][j] + min(down, diagonal)

def min_sum_path(triangle):
    return min_sum_path_rec(triangle, 0, 0)

if __name__ == "__main__":
    triangle = [
        [2],
        [3, 7],
        [8, 5, 6],
        [6, 1, 9, 3]
    ]
    print(f"最小路径和: {min_sum_path(triangle)}")

性能分析：

虽然代码简洁，但这种方法的时间复杂度是指数级的 $O(2^{N^2})$（其中 N 是行数）。为什么会这样？因为我们在重复计算大量的子问题。例如，从 INLINECODEda4eb437 出发到 INLINECODE60a51501 的路径会被计算多次。当三角形变大时，这种低效是不可接受的。

方法二：记忆化搜索（自顶向下的动态规划）

既然我们知道递归慢在重复计算，那么一个自然的优化思路就是：算过一次就记住它。

我们可以创建一个与三角形大小相同的二维数组 INLINECODE8fab2a4b，用来存储从每个位置 INLINECODE15443008 到底部的最小路径和。每次递归前，先检查 INLINECODE103e4fc8 是否已经有值，如果有，直接返回；如果没有，计算出来并存入 INLINECODE27eaf3e9。

#### C++ 记忆化实现

#include 
#include 
#include 
#include 
using namespace std;

// 全局或类成员的 memo 表
int memo[1000][1000]; // 假设三角形最大行数为1000

int minSumPathMemo(vector<vector>& triangle, int i, int j) {
    // 基本情况
    if (i == triangle.size())
        return 0;

    // 检查是否已经计算过
    // 注意：在初始化时我们需要将 memo 表填充为一个特殊值（如 -1）来表示“未计算”
    // 这里为了简化展示，假设在调用主函数前已初始化
    if (memo[i][j] != -1)
        return memo[i][j];

    // 计算并存入 memo 表
    memo[i][j] = triangle[i][j] + min(
        minSumPathMemo(triangle, i + 1, j),
        minSumPathMemo(triangle, i + 1, j + 1)
    );

    return memo[i][j];
}

// 初始化 wrapper
int findMinPath(vector<vector>& triangle) {
    // 初始化 memo 表为 -1
    for(int i=0; i<1000; i++)
        for(int j=0; j<1000; j++)
            memo[i][j] = -1;
            
    return minSumPathMemo(triangle, 0, 0);
}

这种方法将时间复杂度降低到了 $O(N^2)$，因为我们每个单元格只计算一次。空间复杂度主要取决于递归栈的深度和 memo 数组的大小，即 $O(N^2)$。

方法三：制表法（自底向上的动态规划）

虽然记忆化搜索很有效，但在某些语言中（如 Java 或 Python），过深的递归可能会导致栈溢出。更稳健的方法是使用迭代的动态规划，也就是制表法。

思路转换：

与其从顶部开始向下分解，不如直接从底部开始构建。

  • 状态定义： INLINECODE07504629 表示从位置 INLINECODE62b0119d 到达底部的最小路径和。
  • 初始化： dp 的最后一行直接等于三角形的最后一行。
  • 状态转移： 从倒数第二行开始向上遍历。对于 INLINECODE357e771f，它的值取决于 INLINECODE65f9d967。

这种方法的优点是不需要递归栈，且逻辑通常更加清晰。

#### Java 实现制表法

import java.util.ArrayList;
import java.util.List;

class TrianglePath {
    static int minSumPathTab(List<List> triangle) {
        int n = triangle.size();
        
        // 如果三角形为空
        if (n == 0) return 0;

        // 创建 DP 表，大小与三角形一致
        int[][] dp = new int[n][n];

        // 1. 初始化：复制最后一行的数据到 DP 表
        // 最后一行的 dp 值就是其自身的值，因为下面没有路了
        for (int j = 0; j = 0; i--) {
            for (int j = 0; j <= i; j++) {
                // 状态转移方程：
                // 当前点 + min(正下方的点, 右下方的点)
                int down = dp[i + 1][j];
                int diagonal = dp[i + 1][j + 1];
                
                dp[i][j] = triangle.get(i).get(j) + Math.min(down, diagonal);
            }
        }

        // 3. 结果：顶点的值即为全局最小路径和
        return dp[0][0];
    }

    public static void main(String[] args) {
        List<List> triangle = new ArrayList();
        triangle.add(List.of(2));
        triangle.add(List.of(3, 7));
        triangle.add(List.of(8, 5, 6));
        triangle.add(List.of(6, 1, 9, 3));

        System.out.println("最小路径和 (Tabulation): " + minSumPathTab(triangle));
    }
}

预期方法：空间优化的动态规划

作为追求极致性能的开发者，你可能会发现上述的 dp 表其实有浪费。

观察：

当我们从下往上计算时，计算 INLINECODEc217bffd 只需要 INLINECODE1e7633e9 行的数据。一旦 INLINECODE27f0e14b 行计算完毕，INLINECODE642d685e 行的数据就不再需要了。这意味着，我们不需要维护一个 $N imes N$ 的二维数组，只需要维护一个大小为 $N$ 的一维数组即可。

这便是空间优化的核心技巧：滚动数组（或者更准确地说是降维）。

#### C# 实现空间优化版

using System;
using System.Collections.Generic;
using System.Linq;

class GFG {
    static int MinSumPathSpaceOptimized(List<List> triangle) {
        int n = triangle.Count;
        if (n == 0) return 0;

        // dp 数组只需要存储当前行正在计算的数据，
        // 但因为我们是从下往上算，初始时它存储的是最后一行的数据。
        int[] dp = new int[n];

        // 初始化 dp 数组为三角形的最后一行
        for (int j = 0; j = 0; i--) {
            // 关键点：每行的第 j 个位置会覆盖 dp[j]
            // 而计算需要 dp[j] (原下一行同列) 和 dp[j+1] (原下一行下一列)
            for (int j = 0; j <= i; j++) {
                // 状态转移：
                // dp[j] 代表 (i+1, j) 的最小和
                // dp[j+1] 代表 (i+1, j+1) 的最小和
                // 我们用当前 triangle[i][j] 加上两者中的较小值，更新回 dp[j]
                dp[j] = triangle[i][j] + Math.Min(dp[j], dp[j + 1]);
            }
        }

        // 最终，dp[0] 存储的就是顶点的最小路径和
        return dp[0];
    }

    static void Main() {
        List<List> triangle = new List<List> {
            new List {2},
            new List {3, 7},
            new List {8, 5, 6},
            new List {6, 1, 9, 3}
        };

        Console.WriteLine("最小路径和: " + MinSumPathSpaceOptimized(triangle));
    }
}

深度解析与实战建议

在这篇文章中，我们探索了四种不同的解法。你可能会问：实际面试或工作中应该用哪种？

#### 1. 性能对比

  • 递归： 代码最短，但时间复杂度 $O(2^{N^2})$ 毫无实用价值，仅用于理解问题定义。
  • 记忆化： 适合快速将递归代码优化，避免了栈溢出风险（虽然仍依赖递归深度），且逻辑直观。
  • 制表： 最稳健的迭代写法，时间复杂度 $O(N^2)$，空间 $O(N^2)$。
  • 空间优化： 这是预期方法。它同样在 $O(N^2)$ 时间内运行，但将空间复杂度降低到了 $O(N)$（仅依赖一行数组）。对于大型数据集，这能显著减少内存占用。

#### 2. 常见陷阱

  • 索引越界： 在处理三角形时，尤其是右下角的 INLINECODE735c517c 和 INLINECODE42a73886，很容易超出数组边界。务必注意循环的范围 j <= i。
  • 原地修改： 有些同学喜欢直接修改输入的 INLINECODE082eed1e 数组作为 INLINECODEcdeeb582 表。虽然这能节省 $O(N^2)$ 空间，但在实际工程中会破坏输入数据，导致难以调试。除非确定输入不再使用，否则建议另开 dp 数组。
  • 初始化问题： 在使用记忆化搜索时，必须将 memo 表初始化为一个特殊值（如 -1），因为路径和可能包含 0 或负数。如果用 0 初始化，可能会导致误判。

#### 3. 扩展应用

这种“从底层向上构建最优解”的动态规划思想，不仅适用于三角形，还广泛应用于：

  • 最短路径问题： 类似于 Dijkstra 算法在网格图上的应用。
  • 矩阵路径问题： 如“最小路径和”，区别在于只能向右或向下移动。

总结

通过解决“三角形最小路径和”问题，我们不仅学会了一道具体的算法题，更重要的是掌握了如何从递归演进到动态规划的完整思维链路。

  • 识别重叠子问题是优化的第一步。
  • 记忆化是快速优化的手段。
  • 状态转移方程是解决问题的核心。
  • 空间优化是体现工程师专业素养的关键。

建议你亲自尝试编写一遍上述代码，特别是空间优化的版本，体会一下 dp[j] 如何被不断复用和更新的过程。希望这篇文章能帮助你彻底拿下这类动态规划问题！

如果你觉得这篇文章对你有帮助，欢迎分享给你的朋友或在评论区留下你的疑问。

声明：本站所有文章，如无特殊说明或标注，均为本站原创发布。任何个人或组织，在未征得本站同意时，禁止复制、盗用、采集、发布本站内容到任何网站、书籍等各类媒体平台。如若本站内容侵犯了原著者的合法权益，可联系我们进行处理。如需转载，请注明文章出处豆丁博客和来源网址。https://shluqu.cn/32535.html
点赞
0.00 平均评分 (0% 分数) - 0 票

相关文章美国1G带宽/1T流量高速vps $17.99/年