java - 如何让这个方法结束递归并达到最大值？

Question

在运行我编写的作业解决方案时，我遇到了 StackOverflowError。

这些是《Java 方法:A 和 AB》一书中的确切说明:

Write a program in which Cookie Monster finds the optimal path from the upper left corner (0,0) to the lower right corner(SIZE-1,SIZE-1) in a cookie grid (a 2-D array). The elements of the grid contain cookies (a non-negative number) or barrels (-1). On each step, Cookie Monster can only go down or to the right. He is not allowed to step on barrels. The optimal path contains the largest number of cookies.

The program reads the cookie grid from a file and reports the number of cookies on the optimal path. (The path itself is not reported.) A sample data file is provided in JM\Ch19\Exercises\cookies.dat.

Hint: Use a stack. If there is only one way to proceed from the current position, then go there and update the total accumulated number of cookies. If there are two ways to proceed, save one of the possible two points (and its total) on the stack and proceed to the other point. If you have reached the lower-right corner, update the maximum. If there is nowhere to go, examine the stack: pop a saved point, if any, and resume from there.

目标是为我的老师提供最佳的路径(上面有最多“cookie”的路径)。

好的。所以提到的cookie映射文件是这样的:

 1  3  0  5 -1  7 -1 -1  0  4  2  1
-1  3  2  1 -1  4 -1  5  3 -1  1  0
 5  4  8 -1  3  2  2 -1  4 -1  0  0
 2  1  0  4  1 -1  8  0  2 -1  2  5
 1  4  0  1 -1  0  3  2  2  4  1  4
 0  1  4  1  1  6  1  4  5  2  1  0
 3  2  5  2  0  7 -1  2  1  0 -1  3
 0 -1  4 -1 -1  3  5  1  4  2  1  2
 5  4  8 -1  3  2  2 -1  4 -1  0  0
 2  1  0  4  1 -1  8  0  2 -1  2  5
 1  3  0  5 -1  7 -1 -1  0  4  2  1
 0  0  3  1  5  2  1  5  4  1  3  3

这是我用来获取二维数字数组的类(我知道这部分有效。)使用 BlueJ 调试器，二维数组似乎就是我想要的。

import java.util.*;
import java.io.*;

public class MapReader
{
    public static int[][] grid;
    public static Scanner gridscanner = null;
    public static int[][] getMap()
    {
        File file = new File("cookies.dat");
        try
        {
            gridscanner = new Scanner(file);
        }
        catch (FileNotFoundException ex)
        {
            System.out.println("*** Cannot open cookis.dat ***");
            System.exit(1);
        }

        int row = 12;
        grid = new int[row][row];

        for(int r = 0; r < row; r++)
        {
            for(int c = 0; c < row; c++)
            {
                grid[r][c] = gridscanner.nextInt();
            }
        }
        return grid;
    }
}

这是一个我用来跟踪保存的位置、它们的值以及当我遍历这个“cookie map ”时它们的位置的类:

import java.util.*;

public class Point
{
    int row;
    int col;
    int total;

    public Point(int r, int c, int t)
    {
        row = r;
        col = c;
        total = t;
    }

    public int getRow()   { return row; }
    public int getCol()   { return col; }
    public int getValue() { return MapReader.getMap()[row][col]; }
    public int getTotal() { return total; }
}

最后，这是我用来递归遍历二维数组的类。您会注意到，当有两条路径可用时，我更喜欢向右走，但当我从“已保存”堆栈中弹出一个点时，我更喜欢向下走。据我所知，问题就出在这个类上:如何让该方法结束递归并达到最大值？

import java.util.*;

public class CookieMonster
{
    private static int[][] map = MapReader.getMap();
    private static int max = 11;
    private static int total, maximum;
    private static Stack<Point> saved = new Stack<Point>();
    public static void main(String[] args)
    {        
        System.out.println(move(0,0));
    }

    public static int move(int r, int c)
    {
        int right = 0;
        int down = 0;
        boolean isright = true;
        boolean isdown = true;
        if (c < max)
        {
            right = map[r][c + 1];
        }
        else
            isright = false;
        if (r < max)
        {
            down = map[r + 1][c];
        }
        else
            isdown = false;
        if (right == -1)
            isright = false;
        if (down == -1)
            isdown = false;

        if (isright && isdown)
        {
            saved.push(new Point(r + 1, c, total + down));
            total += right;
            move(r, c + 1);
        }

        else if (isright)
        {
            total += right;
            move(r, c + 1);
        }

        else if (isdown)
        {
            total += down;
            move(r + 1, c);
        }

        else
        {
            if (r  == max && c == max)
            {
                if (maximum < total)
                    maximum = total;
            }
            if (!saved.isEmpty())
            {
                Point sd = saved.pop();
                total = sd.getTotal();
                move(sd.getRow(), sd.getCol());
            }
        }
        return maximum;
    }
}

Answer 1

我知道提示建议使用堆栈，但是使用 dynamic programming 可以更有效地解决这个问题。 。它基本上是递归，并记住以前访问过的路径以避免重新计算。

假设您从 1 开始对矩阵进行索引，您的成本函数应如下所示:

c(i, j) = -INF if i == 0 or j == 0 or data(i, j) < 0
          data(1, 1) if i == 1 and j == 1
          data(i, j) + min(c(i, j - 1), c(i - 1, j)) 

您可以在通常的嵌套 i-j 循环中从左到右、从上到下进行迭代。

c(n, n) 将为您提供最佳路径的结果。