当我使用 for 循环时出现 stackoverflow 错误，但如果使用 if 块完成相同的操作，则不会产生错误

Question

我正在解决 DSA 问题
我使用的语言是 java SE
链接：https://www.codingninjas.com/studio/problems/ninja-s-training_3621003
我知道我的解决方案是正确的，但对于其中一个测试用例（我不知道测试用例是什么，因为它不显示测试用例），我遇到了 stackoverflow 错误，所以我只是用一些 if 语句替换了 for 循环，它修复了它，我想知道为什么我首先遇到这个错误

c++ 中的相同解决方案（使用 for 循环）也没有错误，堆栈空间对于 java 和 c++ 的工作方式是否不同？

这两种方法中的函数调用量保持相同，但其中一种方法给出了 stackoverflow 错误，这是没有意义的。所以调用次数不可能超过堆栈空间，如果有人能为我解决这个问题那就太好了

这是带有 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;
    }
}

这是带有 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;
    }
}

Answer 1

第一个解决方案使用额外的局部变量

k

和

cur

，它们在堆栈上为递归函数的每个执行上下文分配。这意味着您的堆栈增长速度比第二个解决方案要快一些。

java 和 c++ 的堆栈空间工作方式不同吗？

是的，每种语言环境都有自己的限制来管理堆栈。它们通常也允许更改堆栈的最大大小。请参阅 了解 Java 和 了解 C++。

注意，你也可以避开

if

方块，一次性处理这三种情况：

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