I have written this Dp code for this problem but why I am getting TLE in a particular test case I am not getting.
Please help me anyone ,
Code – >
#include <bits/stdc++.h>
using namespace std;
int dp[17002][17002];
long long pre[17002];
int f(int i ,int j)
{
if(dp[i][j]!=-1)
return dp[i][j];
if(i>j)
return 0;
if(i==j)
return 0;
int ret = 0;
for(int k = i;k<j;k++)
{
if((pre[k]-pre[i-1]) == (pre[j]-pre[k]))
{
ret = max(ret , 1+max(f(i,k),f(k+1,j)));
}
}
return dp[i][j] = ret;
}
signed main(void)
{
int t;cin>>t;
while(t–){
int n,tt;
cin>>n;
pre[0] = 0;
for(int i =1;i<=n;i++)
{
cin>>tt;
pre[i] = pre[i-1]+tt;
}
for(int i =0;i<=n;i++)
for(int j =0;j<=n;j++)
dp[i][j] =-1;
cout<<f(1,n)<<endl;
}
}