Рекурсивная память Java

Решаю проблему в codeforces. Программирую на Java.

В этой задаче я создаю массив dp[N][5][3] целых чисел (примерно N*5*3 рекурсивных вызовов). Когда N равно миллиону, моя программа падает в памяти, однако лимит памяти составляет около 256 MB. То же решение на C++ идет хорошо, при этом съедает в два раза меньше памяти. Почему это так?

Вот код:

    private int MAX = (int) 1E6 + 6;
    private int[] cnt;
    private int[][][] dp;

    private int min(int a, int b) {
        return a > b ? b : a;
    }

    private int max(int a, int b) {
        return a < b ? b : a;
    }

    private int solve(int x, int t1, int t2) {
        // element x,   x used t1 times,   x + 1 used t2 times
        if (dp[x][t1][t2] != -1)
            return dp[x][t1][t2];
        else if (x + 3 > MAX)
            return dp[x][t1][t2] = (cnt[x] - t1) / 3 + (cnt[x + 1] - t2) / 3;

        int ans0, ans1 = 0, ans2 = 0;
        ans0 = (cnt[x] - t1) / 3 + solve(x + 1, t2, 0);
        int min = min(cnt[x] - t1, min(cnt[x + 1] - t2, cnt[x + 2]));
        if (min >= 1)
            ans1 = (cnt[x] - t1 - 1) / 3 + 1 + solve(x + 1, t2 + 1, 1);
        if (min >= 2)
            ans2 = (cnt[x] - t1 - 2) / 3 + 2 + solve(x + 1, t2 + 2, 2);
        return dp[x][t1][t2] = max(ans0, max(ans1, ans2));
    }

    private void solve(InputReader in, PrintWriter out) {
        int n = in.nextInt();
        int m = in.nextInt();

        cnt = new int[MAX];
        for (int i = 0; i < n; i++) cnt[in.nextInt()]++;

        dp = new int[MAX][5][3];
        for (int i = 0; i <= m; i++)
            for (int j = 0; j < 5; j++)
                for (int k = 0; k < 3; k++)
                    dp[i][j][k] = -1;

        out.println(solve(1, 0, 0));
    }

Нет необходимости понимать логику функции решения. Здесь рекурсивный метод просто вызывается примерно N*5*3 раз.