Saya mendapat ralat stackoverflow apabila saya menggunakan gelung for, tetapi jika perkara yang sama dilakukan menggunakan blok if, ia tidak menghasilkan ralat

Editor PHP Strawberry akan membawa anda meneroka masalah biasa dalam pengaturcaraan Java: ralat stackoverflow berlaku apabila menggunakan gelung for, tetapi tiada ralat berlaku apabila menggunakan blok if. Fenomena ini mungkin disebabkan oleh panggilan berulang gelung for yang menyebabkan limpahan tindanan, dan blok if mengelakkan situasi ini. Masalah ini boleh difahami dengan lebih baik dan diselesaikan dengan analisis mendalam tentang punca masalah dan mekanisme pengurusan memori Java.

Isi soalan

Saya sedang menyelesaikan masalah dsa

Bahasa yang saya gunakan ialah java se

Pautan: https://www.codingninjas.com/studio/problems/ninja-s-training_3621003

Saya tahu penyelesaian saya betul, tetapi untuk salah satu kes ujian (saya tidak tahu apa itu kes ujian kerana ia tidak menunjukkan kes ujian) Saya mendapat ralat stackoverflow, jadi saya hanya menggantikan gelung for dengan beberapa jika kenyataan , ia telah ditetapkan, saya tertanya-tanya mengapa saya mendapat ralat di tempat pertama

Penyelesaian yang sama dalam c++ (menggunakan untuk gelung) juga berfungsi tanpa ralat, adakah ruang tindanan berfungsi secara berbeza dalam java dan c++?

Jumlah panggilan fungsi dalam kedua-dua kaedah tetap sama, tetapi salah satu kaedah memberikan ralat stackoverflow, yang tidak masuk akal. Jadi bilangan panggilan tidak boleh melebihi ruang tindanan, alangkah baiknya jika seseorang dapat menyelesaikan masalah ini untuk saya

Ini ialah kod dengan untuk gelung:

public class solution {
    private static int dp[][];
    private static int rec(int day, int prev, int[][] points) {
        if (day == 0) {
            // no more days left.
            return 0;
        }

        if (dp[day][prev] != -1) {
            return dp[day][prev];
        }

        // merit points of ith task on nth day.
        int ans = points[day - 1][prev - 1];
        int mx = 0;
        for(int k=1;k<4;k++)
        {
            if(k!=prev)
            {
                int cur=rec(day-1, k, points);
                mx=math.max(cur,mx);
            }
        }
        

        dp[day][prev] = ans + mx;
        return ans + mx;
    }

    public static int ninjatraining(int n, int points[][]) {
        // dp table to memoize the solution.
        dp = new int[n + 1][4];
        for (int i = 0; i <= n; i++) {
            for (int j = 0; j < 4; j++) {
                dp[i][j] = -1;
            }
        }
        int ans = 0;
        ans = math.max(ans, rec(n, 1, points));
        ans = math.max(ans, rec(n, 2, points));
        ans = math.max(ans, rec(n, 3, points));

        return ans;
    }
}

Berikut ialah kod dengan blok jika:

public class Solution {
    private static int dp[][];
    private static int rec(int day, int prev, int[][] points) {
        if (day == 0) {
            // No more days left.
            return 0;
        }

        if (dp[day][prev] != -1) {
            return dp[day][prev];
        }

        // Merit points of ith task on nth day.
        int ans = points[day - 1][prev - 1];
        int mx = 0;
        
        if (prev == 1) {
            mx = Math.max(rec(day - 1, 2, points), rec(day - 1, 3, points));
        }

        if (prev == 2) {
            mx = Math.max(rec(day - 1, 1, points), rec(day - 1, 3, points));
        }

        if (prev == 3) {
            mx = Math.max(rec(day - 1, 1, points), rec(day - 1, 2, points));
        }

        dp[day][prev] = ans + mx;
        return ans + mx;
    }

    public static int ninjaTraining(int n, int points[][]) {
        // DP table to memoize the solution.
        dp = new int[n + 1][4];
        for (int i = 0; i <= n; i++) {
            for (int j = 0; j < 4; j++) {
                dp[i][j] = -1;
            }
        }
        int ans = 0;
        ans = Math.max(ans, rec(n, 1, points));
        ans = Math.max(ans, rec(n, 2, points));
        ans = Math.max(ans, rec(n, 3, points));

        return ans;
    }
}

Penyelesaian

Penyelesaian pertama menggunakan pembolehubah tempatan tambahan k 和 cur yang diperuntukkan pada tindanan untuk setiap konteks pelaksanaan fungsi rekursif. Ini bermakna timbunan anda akan berkembang sedikit lebih cepat daripada penyelesaian kedua.

Ya, setiap tempat mempunyai batasan tersendiri untuk mengurus timbunannya. Mereka juga biasanya membenarkan menukar saiz maksimum timbunan. Lihat untuk Java dan untuk C++.

Perhatikan bahawa anda juga boleh mengelakkan if blok dan mengendalikan ketiga-tiga kes sekaligus:

int mx = Math.max(rec(day - 1, prev % 3 + 1, points), 
                  rec(day - 1, (prev + 1) % 3 + 1, points));

Anda boleh menjimatkan lebih banyak ruang tindanan jika anda menyimpan mata sebagai pembolehubah statik (sama seperti dp) dan tidak menghantarnya sebagai parameter kepada fungsi rekursif. points 存储为静态变量（就像 dp 一样）并且不将其作为参数传递给递归函数，则可以减少更多堆栈空间。

用于获取递归函数结果的堆栈由于测试中可能存在很大的输入数字 n，分配给 int cur

Timbunan digunakan untuk mendapatkan hasil fungsi rekursif Disebabkan kemungkinan nombor input besar n dalam ujian, peruntukan kepada int cur akan melimpah.

https://www.php.cn/link/efc9ea3e0c2ed2c2481fe1252019266e

🎜

Atas ialah kandungan terperinci Saya mendapat ralat stackoverflow apabila saya menggunakan gelung for, tetapi jika perkara yang sama dilakukan menggunakan blok if, ia tidak menghasilkan ralat. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!