为何这段Java递归动态规划代码会抛出数组越界异常？

一、数组越界异常的根本原因 #

Java数组采用0起始索引，长度为n的数组，有效索引范围是0到n-1。

看最初的代码：

• count(int r, int c)里创建的dp数组是new int[r][c]，比如调用count(3,3)时，dp的行、列有效索引都是0~2。
• 但helper(r, c, dp)直接把传入的r、c当作数组索引使用，比如r=3、c=3时，会尝试访问dp[3][3]，超出了数组的有效索引范围，直接触发ArrayIndexOutOfBoundsException。

更新后的代码里，小输入（比如(1,1)、(2,3)）能正常运行，是因为这些输入的r、c值刚好在new int[4][4]数组的有效索引范围内（比如(2,3)对应索引2和3，4x4数组的列索引最大是3）；但如果调用count(18,18, dp)，18远大于数组的最大索引3，同样会触发越界异常。

二、大输入（如18,18）问题的解决方法 #

大输入的问题包含两个核心点：数组大小不匹配、整数类型溢出。

1. 保证DP数组的大小适配输入 #

你的代码逻辑是1起始索引（判断条件用r==1 || c==1），所以创建DP数组时，应该创建r+1行c+1列的数组，这样索引1_r、1c都是有效的。比如处理(18,18)时，需要创建new int[19][19]（或对应long/BigInteger类型的数组）。

2. 解决整数溢出问题 #

18x18网格的路径数是组合数C(34,17)，结果为2333606220，这个值已经超过了Javaint类型的最大值（2^31-1=2147483647），用int存储会溢出得到错误的负数结果。需要改用更大的数值类型：

• long类型：最大值为9223372036854775807，足够容纳(18,18)甚至(20,20)的路径数（C(38,19)=35345263800）。
• BigInteger类型：支持任意精度的整数运算，能处理更大的输入（比如(30,30)的路径数）。

修复后的代码示例 #

long版本（适合中等大小输入）

public class Maze {
    public static long count(int r, int c, long[][] dp) {
        if (r == 1 || c == 1) {
            return dp[r][c] = 1;
        }
        if (dp[r][c] == 0) {
            dp[r][c] = count(r - 1, c, dp) + count(r, c - 1, dp);
        }
        return dp[r][c];
    }

    public static void main(String[] args) {
        int targetR = 18, targetC = 18;
        // 创建r+1行c+1列的数组，适配1起始索引逻辑
        long[][] dp = new long[targetR + 1][targetC + 1];
        System.out.println(count(targetR, targetC, dp)); // 输出2333606220
    }
}

BigInteger版本（适合超大输入）

import java.math.BigInteger;

public class Maze {
    public static BigInteger count(int r, int c, BigInteger[][] dp) {
        if (r == 1 || c == 1) {
            return dp[r][c] = BigInteger.ONE;
        }
        // BigInteger默认初始值为null，所以判断是否未初始化
        if (dp[r][c] == null) {
            dp[r][c] = count(r - 1, c, dp).add(count(r, c - 1, dp));
        }
        return dp[r][c];
    }

    public static void main(String[] args) {
        int targetR = 18, targetC = 18;
        BigInteger[][] dp = new BigInteger[targetR + 1][targetC + 1];
        System.out.println(count(targetR, targetC, dp)); // 输出2333606220

        // 处理更大的输入，比如30x30
        targetR = 30; targetC = 30;
        dp = new BigInteger[targetR + 1][targetC + 1];
        System.out.println(count(targetR, targetC, dp)); // 输出结果为C(58,29)的数值
    }
}

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