使用 Memoization 解决 Grid Traveler 问题时出现奇怪的值？

Question

我正在学习动态规划，并且刚刚开始解决一些简单的问题。我正在做一个网格旅行者问题，你从网格的左上角开始，只能向左或向下移动。您需要返回从网格左上角到右下角的唯一路径的数量。

当我尝试一些更大的网格时，我得到一些奇怪的返回值。例如，当我尝试 (18,18) 时，它会转到 -> -1961361076 而不是 2333606220

任何人都可以看到我的代码有问题吗？

'''

import java.util.HashMap;

public class Test{

    public static void main(String[] args){
        HashMap<String, Integer> memo = new HashMap<>();
        System.out.println(gridTraveler(2,2,memo));
        System.out.println(gridTraveler(18,18,memo));
    }

    public static int gridTraveler(int m, int n, HashMap<String, Integer> memo){

        String key = "" + m + "," + n;
        //base case
        if(m == 1 || n == 1)
            return 1;

        //base case
        if(m == 0 || n == 0)
            return 0;

        if (memo.containsKey(key))
            return memo.get(key);

        //Set value of the key memo[key]
        memo.put(key, gridTraveler(m-1, n, memo) + gridTraveler(m, n-1, memo));

        return memo.get(key);
    }
}

Answer 1

这是因为已达到 Integer 的最大值。当您尝试向其添加值时，它会溢出，并“环绕”到负值。

如果更改为 Long 而不是 Integer，它将起作用：-

public static void main(String[] args){
    HashMap<String, Long> memo = new HashMap<>();
    System.out.println(gridTraveler(2,2,memo));
    System.out.println(gridTraveler(18,18,memo));
}

public static Long gridTraveler(long i, long j, HashMap<String, Long> memo){

    String key = "" + i + "," + j;
    //base case
    if(i == 1 || j == 1)
        return (long) 1;

    //base case
    if(i == 0 || j == 0)
        return (long) 0;

    if (memo.containsKey(key))
        return memo.get(key);

    //Set value of the key memo[key]
    memo.put(key, gridTraveler(i-1, j, memo) + gridTraveler(i, j-1, memo));

    return memo.get(key);
}
}

Answer 2

Java中的int数据类型是4个字节长（32位） 由于格式是有符号的，意味着32位中的最高有效位代表数字的符号（0=正，1=负） 在这种情况下， int 的最大正值是 (2^31)-1，即 2,147,483,647，小于您的预期输出。 （这也会导致最高有效位变为 1，从而解释负值） 因此，您应该使用 8 字节（64 位）的 long