在 geeksforgeeks 上解决矩阵问题中的路径有什么问题？

Question

你能帮我解决这个 geeksforgeeks 问题
给定一个 NXN 矩阵 Matrix[N][N] 的正整数。从一个单元格 Matrix[r][c] 中只有三种可能的移动。

1. 矩阵[r+1][c]

2. 矩阵[r+1][c-1]

3. 矩阵[r+1][c+1]

从第 0 行的任何列开始，返回直到第 N-1 行的任何路径的最大总和。

问题链接：https : //practice.geeksforgeeks.org/problem-page.php?pid=271

解决方案链接：https : //ide.geeksforgeeks.org/R5iu3xwTAO

import java.util.*;

public class Main {

    public static void main(String[] args) {

        Scanner sc = new Scanner(System.in);

        int t  =1;

        int n;

        int a[][];

        while(t-->0){

            n = 17;

            a = new int [n][n];

            int input[]={67,280,171,381,930,781,925,4,393,380,246,433,762,258,5,166,315,503,385,728,854,350,464,288,304,80,689,56,313,843,92,379,122,614,111,403,394,387,406,138,767,651,571,880,260,927,398,926,429,782,653,634,132,468,274,435,548,314,490,212,156,933,942,629,546,404,31,292,142,436,781,260,86,703,140,697,630,537,622,410,318,275,44,801,94,669,236,993,982,77,204,137,10,497,765,907,900,147,550,42,582,331,301,19,33,792,715,14,680,336,424,350,962,467,150,408,135,737,400,468,814,956,956,175,452,72,433,704,218,983,97,799,665,749,169,49,541,883,63,572,570,486,921,884,304,423,291,790,159,42,257,324,997,212,498,801,283,283,504,500,617,952,650,281,700,818,329,592,52,743,164,621,228,436,856,883,858,498,672,17,540,928,340,536,139,190,336,773,472,191,272,88,142,921,720,842,90,400,433,141,143,948,114,722,384,969,605,593,819,276,961,358,556,301,893,46,842,581,819,665,771,90,104,265,363,823,106,452,574,890,945,68,190,58,790,925,378,746,517,196,373,478,905,280,130,798,326,323,730,144,987,500,585,90,764,947,264,221,751,837,463,47,257,652,456,46,576,185,143,444,381,867,921,285,147,402,434,472,724,163,615,710,15,551,151,130,498,414,703};

            int k=0;

            for(int i=0;i<n;i++){

                for(int j=0;j<n;j++){

                    a[i][j] = input[k];

                    k++;

                }

            }

这应该给出输出 13785 但它给出 10689

Answer 1

代码中有两个小错误：r&nbsp;=&nbsp;a[x][y]+&nbsp;Math.max(Math.max(CostPath(a,x+1,y,h),CostPath(a,x+1,y-1,h)),CostPath(a,x+1,y-1,h));是错误的（CostPath(a,x+1,y-1,h)计算了两次）应该是：r&nbsp;=&nbsp;a[x][y]+&nbsp;Math.max(Math.max(CostPath(a,x+1,y,h),CostPath(a,x+1,y-1,h)),CostPath(a,x+1,y+1,h));和这个System.out.println(ans);应该改为System.out.println(max);进行这两个更改后，输出是正确的。旁注：没有必要将无效的 x,y 值添加到地图路径中。防止它并使程序更有效地更改r=&nbsp;Integer.MIN_VALUE;到return&nbsp;0;