Java实现N*N矩阵最大平均路径代码错误排查求助

首先，咱们来梳理下问题：从N×N矩阵的左上角走到右下角，只能向右或向下移动，要找出平均代价最大的路径（平均代价=路径总代价÷经过的单元格数）。你的代码目前无法得到正确结果，主要有以下几个核心问题：

1. 贪心策略不适用 #

你试图每次选择当前位置右边或下边中代价更大的单元格，这种“只看眼前最优”的贪心思路无法保证全局最优。举个例子：假设存在一条路径，某一步选了较小的单元格，但后续跟着多个高代价单元格，最终的平均代价反而更高——贪心会直接错过这类更优路径。

2. 数组越界问题 #

当遍历到矩阵的最后一行（i = n-1）时，i+1 = n，访问c[i+1][j]会直接触发数组越界异常；同理，遍历到最后一列（j = n-1）时，j+1 = n，访问c[i][j+1]也会越界。你的代码完全没处理边界情况，运行时大概率会崩溃。

3. 路径遍历逻辑完全错误 #

你的双重循环会遍历矩阵的每一个单元格，并且每次循环都执行一次加法操作——这根本不是在模拟单条从左上到右下的路径，而是无意义地重复累加大量单元格。比如对于3×3的矩阵，你的循环会执行9次，sum会累加9个值，m会变成9，但实际合法路径的单元格数是2n-1=5，这直接导致计算出的平均完全错误。

正确解法：动态规划 #

我们可以用动态规划来记录到达每个单元格的最大总代价，因为路径的平均代价=总代价÷路径长度，而到达单元格(i,j)的路径长度固定为i+j+1（从(0,0)到(i,j)需要走i+j步，加上起点共i+j+1个单元格）。因此，只要保证总代价最大，对应的平均代价就是该路径的最大值。

动态规划思路 #

• 状态定义：dp[i][j]表示从左上角(0,0)到达(i,j)的最大总代价。
• 状态转移：
  • 第一行（只能从左边来）：dp[0][j] = dp[0][j-1] + c[0][j]
  • 第一列（只能从上面来）：dp[i][0] = dp[i-1][0] + c[i][0]
  • 其他位置：dp[i][j] = max(dp[i-1][j], dp[i][j-1]) + c[i][j]（选从上方或左方过来的最大总代价，加上当前单元格代价）
• 最终结果：dp[n-1][n-1] / (2*n - 1)（右下角的最大总代价除以路径长度）

修正后的Java代码 #

import java.util.Scanner;

public class MaxAvgPath {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[][] c = new int[n][n];
        
        // 读取矩阵数据
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                c[i][j] = sc.nextInt();
            }
        }
        
        // 初始化DP数组
        double[][] dp = new double[n][n];
        dp[0][0] = c[0][0];
        
        // 填充第一行
        for (int j = 1; j < n; j++) {
            dp[0][j] = dp[0][j-1] + c[0][j];
        }
        
        // 填充第一列
        for (int i = 1; i < n; i++) {
            dp[i][0] = dp[i-1][0] + c[i][0];
        }
        
        // 填充其他位置
        for (int i = 1; i < n; i++) {
            for (int j = 1; j < n; j++) {
                dp[i][j] = Math.max(dp[i-1][j], dp[i][j-1]) + c[i][j];
            }
        }
        
        // 计算最大平均代价：总代价 / 路径单元格数（2n-1）
        double maxAvg = dp[n-1][n-1] / (2 * n - 1);
        System.out.println(String.format("%.1f", maxAvg)); // 按示例保留一位小数
        
        sc.close();
    }
}

测试示例输入 #

输入：

3
1 2 3
4 5 6
7 8 9

输出：5.8，和预期一致，对应路径1→4→7→8→9，总代价29，29/5=5.8。

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