I was solving a DSA problem
the language I'm using is java SE
link:https://www.codingninjas.com/studio/problems/ninja-s-training_3621003
I know my solution is correct but for one of the test cases(I dont know what the test case is as it doesnt display the test case) I run into a stackoverflow error so I just replaced the for loop with a few if statements and it fixed it, I want to know why I ran into the error in first place

also the same solution(with for loop) in c++ gives no error, does stack space work differently for java and c++?

it just doesnt make sense the amount of function calls made remains the same in both the approaches but one gives a stackoverflow error. so there is no way the the number of calls is more than the stack space, If someone could figure this out for me it'd be great

以下是for loop的代码:

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 blocks的代码:

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

推荐答案

第一种解决方案使用额外的局部变量kcur,它们在堆栈上为递归函数的每个执行上下文分配.这意味着您的堆栈比使用第二种解决方案时增长得更快一些.

堆栈空间在Java和C++中的工作方式是否不同?

是的,每种语言环境管理它们的堆栈都有自己的限制.它们通常还允许更改堆栈的最大大小.请参见for Javafor C++.

请注意,您也可以避免if个块,并一口气处理三个案件:

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

如果将points存储为静态变量(就像dp一样),并且不将其作为参数传递给递归函数,则可以减少更多的堆栈空间.

Java相关问答推荐

使用REST客户端和对象映射器从字符串反序列化Json

为什么Java Annotation接口覆盖对象类中的方法

为什么Java编译器不区分不同类型的方法?

MySQL数据库中未应用具有Spring数据的唯一约束

基于接口的投影、原生查询和枚举

搜索列表返回多个频道

带有Health Check的Spring Boot BuildPack打破了本机映像构建过程

有效的公式或值列表必须少于或等于255个字符

使用Jackson库反序列化json

buildDir:File!&#的getter解决方案是什么?39.被抛弃

在Ubuntu 23.10上使用mp3创建JavaFX MediaPlayer时出错

Spring动态反序列化JSON可以是列表,也可以只是一个对象

IntelliJ IDEA依赖项工具窗口丢失

在Eclipse中可以使用外部字体吗?

用于Java的Visual Studio代码完成不起作用

Java KeyListener不工作或被添加

我该如何为我的类编写getter和setter方法?

放置在变量中的Java成员引用不相等

Maven创建带有特定类的Spring Boot jar和普通jar

在对象列表上调用提取后,如何判断没有值为空?