J'obtiens une erreur stackoverflow lorsque j'utilise une boucle for, mais si la même chose est faite en utilisant un bloc if, cela ne produit pas l'erreur

L'éditeur PHP Strawberry vous amènera à explorer un problème courant dans la programmation Java : une erreur de stackoverflow se produit lors de l'utilisation d'une boucle for, mais aucune erreur ne se produit lors de l'utilisation d'un bloc if. Ce phénomène peut résulter d'appels répétés de la boucle for provoquant un débordement de pile, et le bloc if évite cette situation. Ce problème peut être mieux compris et résolu par une analyse approfondie de la cause première du problème et du mécanisme de gestion de la mémoire Java.

Contenu de la question

Je résous le problème DSA

Le langage que j'utilise est Java se

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

Je sais que ma solution est correcte, mais pour l'un des cas de test (je ne sais pas ce qu'est un scénario de test car il ne montre pas les cas de test), j'ai eu une erreur de débordement de pile, j'ai donc simplement remplacé la boucle for par un if déclarations, cela a été corrigé, je me demande pourquoi j'ai eu l'erreur en premier lieu

La même solution en C++ (en utilisant la boucle for) fonctionne également sans erreur, l'espace de pile fonctionne-t-il différemment en Java et en C++ ?

Le nombre d'appels de fonction dans les deux méthodes reste le même, mais l'une des méthodes génère une erreur de débordement de pile, ce qui n'a aucun sens. Le nombre d'appels ne peut donc pas dépasser l'espace de la pile, ce serait formidable si quelqu'un pouvait résoudre ce problème pour moi

Voici le code avec la boucle for :

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;
    }
}

Voici le code avec le bloc if :

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;
    }
}

Solution

La première solution utilise des variables locales supplémentaires k 和 cur qui sont allouées sur la pile pour chaque contexte d'exécution de la fonction récursive. Cela signifie que votre pile grandira un peu plus vite que la deuxième solution.

Oui, chaque locale a ses propres limites pour gérer sa pile. Ils permettent également généralement de modifier la taille maximale de la pile. Voir pour Java et pour C++.

Notez que vous pouvez également éviter le blocage if et gérer les trois cas en même temps :

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

Vous pouvez économiser plus d'espace sur la pile si vous stockez les points en tant que variable statique (tout comme dp) et ne le transmettez pas en tant que paramètre à la fonction récursive. points 存储为静态变量（就像 dp 一样）并且不将其作为参数传递给递归函数，则可以减少更多堆栈空间。

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

Pile pour obtenir les résultats des fonctions récursives Comme il peut y avoir de grands nombres d'entrée n dans le test, l'allocation à int cur débordera.

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

🎜

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!