Help Needed for problem SUMTRIAN

1

Hi,
I am trying to solve the dp problem:

But it is showing some weird behavior for the input. Whenever I am trying to test with input case one by one it is giving me correct result but while trying to execute the testcases at once it is showing the wrong answere.

Code :

#include<bits/stdc++.h>
using namespace std;

const int N = 100;
vector<vector<int>> dp(N, vector<int>(N, -1));

int solve(vector<vector<int>>& arr , int n,   int i, int j)
{
 if (i == n || j == n)
 {
 	return dp[i][j] = 0;
 }

 if (dp[i][j] != -1)
 	return dp[i][j];

 return dp[i][j] = (arr[i][j] + max(solve(arr, n , i + 1, j)  , solve(arr, n, i + 1, j + 1)));
}

int main()
{
 int t;
 cin >> t;

 while (t--)
 {
 	int n;
 	cin >> n;
 	vector<vector<int>> arr(n, vector<int>(n, 0));

 	for (int i = 0; i < n; i++)
 	{
 		for (int j = 0; j <= i; j++)
 		{
 			cin >> arr[i][j];
 		}
 	}
 	cout << solve(arr, n, 0, 0) << endl;

 	for(int i = 0;i<100;i++)
 	{
 	    dp[i].clear();
 	}
 }
}

Please some could suggest where I am doing mistake.
Thanks.

2

I am not much aware of CPP, but I guess I figured out the bug.

Why are you clearing the DP vector, for every iteration, is it fine?
Try giving two or more inputs at a time i.e., 2 or more test cases.

3

for each test case , since I have declared it globally , to re-initialize its value , I am trying to clear it so that it can be used for the second or forthcoming test cases.

4

Try doing this.

5

Yes I have tried to give the two test case defined in the problem statement , it is giving me the output 5 and 5 for both the test cases

6

Here’s my solution. I don’t understand CPP, frankly.

1 Like
7

@suman_18733097 Thanks a lot for sharing the code :slight_smile:

1 Like
8

clear() will reduce its size to 0.

9

Thanks but how should I re-initialize the vector for each new testcase?

10

You can just store -1 in dp instead of using clear()