Память рекурсии Java

Question

Я решаю проблему в 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 раз.

Answer 1

Это зависит от вашего кода. Прежде всего, если вы работаете с рекурсивным методом, jvm сохраняет каждый объект в куче и содержит ссылку на каждый объект в стеке. Если вы хотите предотвратить эту ошибку, вы должны инициализировать неиспользуемый объект как ноль.

Answer 2

Если вам абсолютно необходим такой большой массив (и я рекомендую вам дважды подумать, прежде чем использовать этот большой массив и искать лучшее решение для памяти), вы можете увеличить максимальный объем памяти Java-программы во время запуска с помощью аргумента -Xmx

Например: java -jar myProgram.jar -Xmx1G для использования 1 ГБ в качестве памяти максимального размера кучи (обратите внимание, что если этого недостаточно, вы можете увеличить еще)

Обратите внимание, что вы также можете указать начальный размер кучи с помощьюаргумент -Xms