Что не так с этим решением для Path in Matrix Problem на geeksforgeeks? - PullRequest
Новая
       14

Что не так с этим решением для Path in Matrix Problem на geeksforgeeks?

0 голосов
/ 23 сентября 2018

Можете ли вы помочь мне с этой проблемой geeksforgeeks
Учитывая матрицу NXN Matrix [N] [N] натуральных чисел.Матрица ячейки [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++;
                }
            }
            HashMap<String,Integer> h = new HashMap();
            int max=Integer.MIN_VALUE,ans=0;
            for(int i=0;i<a.length;i++){
                ans=CostPath(a,0,i,h);
                if(ans>max)
                    max=ans;
            }
            System.out.println(ans);
        }

    }


    public static int CostPath(int a[][],int x,int y,HashMap<String,Integer>h){
        if(h.containsKey(x+","+y))
            return h.get(x+","+y);
        int r;
        if(x>=a.length || y>= a.length || x<0 || y<0 ){
            r= Integer.MIN_VALUE;
        }
        else if(x==a.length-1 ){
            r= a[x][y];
        }

        else{
            r= a[x][y]+Math.max(Math.max(CostPath(a,x+1,y,h),CostPath(a,x+1,y-1,h)),CostPath(a,x+1,y-1,h));
        }
        h.put(x+","+y,r);
        return r;
    }
}

Это должно дать вывод 13785, но это даст 10689

Ответы [ 2 ]

0 голосов
/ 24 сентября 2018

Это решение для динамического программирования.Здесь нет необходимости хранить HashMap, даже сам путь.Заметка;Я удалил информацию о пути, это был 2D-массив для хранения, откуда берется максимум.

Как видите, здесь нет рекурсии.Если вы посмотрите на рекурсию, снизу вы поймете этот код.

Примечание;с вашим входным результатом 13785. 

import java.util.*;

public class path {


    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int t  =1;
        int n;
        int values[][];

        while(t-->0){

            n = 17;
            values = 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++){
                    values[i][j] = input[k];
                    k++;
                }
            }

            for ( int r = n-2 ; r >=0 ; r-- ) {

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

                    if (c == 0) {
                        values[r][c] += Math.max(values[r+1][c], values[r+1][c+1]);

                    } else if (c == n-1) {
                        values[r][c] += Math.max(values[r+1][c], values[r+1][c-1]);
                    } else {
                        values[r][c] += Math.max(values[r+1][c], Math.max(values[r+1][c-1], values[r+1][c+1]));
                    }
                }
            }

            int max = values[0][0];

            for(int c = 1; c <= n-1 ; c++) 
                max = Math.max(max, values[0][c]);

            System.out.println(max);
        }
    }
}
0 голосов
/ 24 сентября 2018

В коде есть две небольшие ошибки: 

r = a[x][y]+ 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 = a[x][y]+ 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= Integer.MIN_VALUE;

на 

return 0;
...