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