二维数组首行起始垂直线最小和递归求解故障排查

我来帮你拆解下当前递归代码里的问题，然后给出能得到正确结果的方案：

你的递归代码存在的核心问题 #

1. 重复累加res参数 #

你把res作为参数传递给递归函数，然后在每一层都执行res += ...，这会导致路径上的元素被重复计算。比如初始调用时res是首行的元素值，下一层递归又带着这个值继续累加，最终结果会包含多次同一元素的求和。

2. 边界条件与元素累加逻辑错误 #

当到达最后一行（x == H - 1）时，你直接给res加上当前元素，但此时res已经包含了前面路径的和，而中间行的元素（比如x=1时的arr[1,y]）并没有被正确加入路径和，导致最终结果缺失部分元素。

3. 未遍历首行所有起始点 #

你的函数只针对单个起始点(x,y)计算路径和，但题目要求的是首行任意点出发的最小路径和，需要遍历首行所有列，计算每个起点的路径和后取最小值。

修正后的递归思路 #

正确的递归逻辑应该是：

• 对于当前位置(x,y)，它的最小路径和 = 当前元素值 + 下一行可到达位置（正下方、左下方、右下方，需注意边界）的最小路径和
• 当到达最后一行时，路径和就是当前元素的值（因为没有下一行了）
• 最后遍历首行所有起始点，计算每个起点的路径和，取其中的最小值作为最终结果

修正后的C#代码示例 #

// 计算从(x,y)出发到最后一行的最小路径和
static int MinPathSum(int[,] arr, int x, int y, int width, int height)
{
    // 到达最后一行，直接返回当前元素的值
    if (x == height - 1)
    {
        return arr[x, y];
    }

    int minNextPath = int.MaxValue;
    // 尝试下一行的左下方位置（如果当前不在最左列）
    if (y > 0)
    {
        minNextPath = Math.Min(minNextPath, MinPathSum(arr, x + 1, y - 1, width, height));
    }
    // 尝试下一行的正下方位置
    minNextPath = Math.Min(minNextPath, MinPathSum(arr, x + 1, y, width, height));
    // 尝试下一行的右下方位置（如果当前不在最右列）
    if (y < width - 1)
    {
        minNextPath = Math.Min(minNextPath, MinPathSum(arr, x + 1, y + 1, width, height));
    }

    // 当前路径和 = 当前元素值 + 下一行的最小路径和
    return arr[x, y] + minNextPath;
}

// 主函数：遍历首行所有起始点，找到最小路径和
static int FindMinTotalPath(int[,] arr, int width, int height)
{
    int minTotal = int.MaxValue;
    for (int y = 0; y < width; y++)
    {
        int currentPathSum = MinPathSum(arr, 0, y, width, height);
        minTotal = Math.Min(minTotal, currentPathSum);
    }
    return minTotal;
}

测试你的示例输入 #

对于输入数组[[1,2,3],[4,5,6],[7,8,9]]，转换为C#二维数组后调用FindMinTotalPath(arr, 3, 3)：

• 从(0,0)出发：1 + (4 + 7) = 12
• 从(0,1)出发：2 + (4 + 7) = 13
• 从(0,2)出发：3 + (5 + 7) = 15
  取最小值12，和预期输出完全一致。

性能优化：记忆化搜索（避免重复计算） #

递归会重复计算大量相同子问题（比如不同路径可能到达同一个(x,y)），我们可以用一个二维缓存数组存储已经计算过的路径和，提升效率：

static int MinPathSumMemo(int[,] arr, int x, int y, int width, int height, int[,] memo)
{
    if (x == height - 1)
    {
        return arr[x, y];
    }

    // 如果已经计算过该位置的路径和，直接返回缓存值
    if (memo[x, y] != 0)
    {
        return memo[x, y];
    }

    int minNextPath = int.MaxValue;
    if (y > 0)
    {
        minNextPath = Math.Min(minNextPath, MinPathSumMemo(arr, x + 1, y - 1, width, height, memo));
    }
    minNextPath = Math.Min(minNextPath, MinPathSumMemo(arr, x + 1, y, width, height, memo));
    if (y < width - 1)
    {
        minNextPath = Math.Min(minNextPath, MinPathSumMemo(arr, x + 1, y + 1, width, height, memo));
    }

    // 缓存当前位置的路径和
    memo[x, y] = arr[x, y] + minNextPath;
    return memo[x, y];
}

static int FindMinTotalPathMemo(int[,] arr, int width, int height)
{
    int minTotal = int.MaxValue;
    int[,] memo = new int[height, width];
    for (int y = 0; y < width; y++)
    {
        int currentPathSum = MinPathSumMemo(arr, 0, y, width, height, memo);
        minTotal = Math.Min(minTotal, currentPathSum);
    }
    return minTotal;
}

这个优化对于较大的二维数组效果尤为明显，能避免大量重复递归调用。

内容的提问来源于stack exchange，提问作者user13674310