Java实现带记忆化的网格旅行者DP问题大网格返回异常值如何解决

问题原因 #

你的代码问题出在整数溢出。
Java 中 int 是 32 位有符号整数，取值范围为 -2147483648 ~ 2147483647。18*18 网格的唯一路径总数是组合数 C(34,17) = 2333606220，这个数值已经超过了 int 的最大值，溢出后符号位翻转，就会返回负数结果。

修复方案 #

把所有存储路径数的变量类型从 int / Integer 改为取值范围更大的 long / Long 即可：

• 修改函数返回值类型为 long
• 把 HashMap 的 value 类型改为 Long
• 基础 case 的返回值改为 long 类型的字面量

修复后的代码如下：

import java.util.HashMap;

public class Test{

    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(int m, int n, HashMap<String, Long> memo){

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

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

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

        memo.put(key, gridTraveler(m-1, n, memo) + gridTraveler(m, n-1, memo));
        return memo.get(key);
    }
}

如果后续需要计算更大尺寸的网格，long 也不足以存储结果时，可以改用 BigInteger 类型实现任意精度的整数存储。

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