代码无输出排查：求解二维矩阵右下方向最大路径和

1. 程序卡住的直接原因：死循环 #

你的maxSum函数里，while (current_Iteration <= max_Iterations)循环从未更新current_Iteration变量，导致循环条件永远成立，程序陷入死循环，自然无法输出任何结果。

2. 算法逻辑错误：贪心策略无法得到全局最优解 #

就算修复了死循环，你当前用的贪心思路（每次选下方或右方数值更大的格子移动）也不能保证拿到全局最大路径和。举个简单反例：

1  100  1
1  1    1

按你的算法会走1→1→1→1→1，总和是5，但实际最优路径是1→100→1→1，总和是103。

3. 修复方案 #

步骤1：临时修复死循环（仅解决卡住问题，算法仍错误） #

在循环末尾添加current_Iteration++，让循环能正常终止：

while (current_Iteration <= max_Iterations)
{
    // 原有的移动判断逻辑
    sum = sum + matrix[i][j];
    current_Iteration++; // 新增这一行
}

步骤2：改用动态规划实现正确的最大路径和 #

动态规划是解决这类网格路径最优问题的标准方法，核心思路是构建一个DP表，dp[i][j]表示从左上角[0][0]到[i][j]的最大路径和，状态转移规则如下：

• 起点[0][0]：dp[0][0] = matrix[0][0]
• 第一行（只能从左侧移动过来）：dp[0][j] = dp[0][j-1] + matrix[0][j]
• 第一列（只能从上方移动过来）：dp[i][0] = dp[i-1][0] + matrix[i][0]
• 其他位置：dp[i][j] = max(dp[i-1][j], dp[i][j-1]) + matrix[i][j]

最终dp[rows-1][columns-1]就是从起点到终点的最大路径和。

修改后的maxSum函数实现：

int maxSum(int matrix[ROW][COL], int rows, int columns)
{
    int dp[ROW][COL];
    dp[0][0] = matrix[0][0];

    // 初始化第一行
    for (int j = 1; j < columns; j++)
    {
        dp[0][j] = dp[0][j-1] + matrix[0][j];
    }

    // 初始化第一列
    for (int i = 1; i < rows; i++)
    {
        dp[i][0] = dp[i-1][0] + matrix[i][0];
    }

    // 填充DP表
    for (int i = 1; i < rows; i++)
    {
        for (int j = 1; j < columns; j++)
        {
            dp[i][j] = (dp[i-1][j] > dp[i][j-1] ? dp[i-1][j] : dp[i][j-1]) + matrix[i][j];
        }
    }

    return dp[rows-1][columns-1];
}

完整修复后的代码 #

#include <stdio.h>
#include <stdlib.h>

#define ROW 10
#define COL 10

void scanMatrix(int[ROW][COL], int, int);
void printMatrix(int[ROW][COL], int, int);

int maxSum(int[ROW][COL], int, int);

int main()
{
    int rows, columns;
    int matrix[ROW][COL];
    int RequiredSum;

    printf("Enter rows and columns of the matrix: ");
    scanf("%d%d", &rows, &columns);

    if (rows <= 0 || columns <= 0)
    {
        printf("Invalid inputs. Rows and Columns must be greater than 0");
        exit(0);
    }

    printf("Enter matrix elements:\n");
    scanMatrix(matrix, rows, columns);

    printf("Matrix elements are:\n");
    printMatrix(matrix, rows, columns);

    RequiredSum = maxSum(matrix, rows, columns);
    printf("Maximum sum: %d", RequiredSum);
}

void scanMatrix(int matrix[ROW][COL], int rows, int columns)
{
    for (int i = 0; i < rows; i++)
        for (int j = 0; j < columns; j++)
            scanf("%d", &matrix[i][j]);
}

void printMatrix(int matrix[ROW][COL], int rows, int columns)
{
    for (int i = 0; i < rows; i++)
    {
        for (int j = 0; j < columns; j++)
            printf("%d ", matrix[i][j]);

        printf("\n");
    }
}

int maxSum(int matrix[ROW][COL], int rows, int columns)
{
    int dp[ROW][COL];
    dp[0][0] = matrix[0][0];

    // 第一行只能从左往右累加
    for (int j = 1; j < columns; j++)
    {
        dp[0][j] = dp[0][j-1] + matrix[0][j];
    }

    // 第一列只能从上往下累加
    for (int i = 1; i < rows; i++)
    {
        dp[i][0] = dp[i-1][0] + matrix[i][0];
    }

    // 其余位置取上方或左方的最大路径和，加上当前元素
    for (int i = 1; i < rows; i++)
    {
        for (int j = 1; j < columns; j++)
        {
            dp[i][j] = (dp[i-1][j] > dp[i][j-1] ? dp[i-1][j] : dp[i][j-1]) + matrix[i][j];
        }
    }

    return dp[rows-1][columns-1];
}

验证示例 #

用之前的测试矩阵输入：

Enter rows and columns of the matrix: 3 3
Enter matrix elements:
1 100 1
1 1 1
1 1 1

程序输出的最大和为103，符合预期。

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