What is wrong with my solution,i want to solve it by dp.
//First solution:
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define v vector<ll>
#define vvi vector<vector<ll>>
const ll MOD = 1000000007;
#define fta_fat() {ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);}
#define loop(st,end) for(int i=st;i<end;i++)
#define revloop(st,end) for(int i=st;i>=end;i--)
#define pb emplace_back
int solve(int arr[],int n,int dp[]){
if(n<=0){
return 0;
}
if(n<=1){
return abs(arr[n-1]);
}
if(dp[n] !=-1){
return dp[n];
}
int ans=arr[0],ans1=arr[1];
while(arr[1]-2>0){
ans -=1;
ans1 -=2;
}
return dp[n]=min((abs(ans)+abs(ans1)+(solve(arr+2,n-2,dp))),(abs(arr[0])+(solve(arr+1,n-1,dp))));
}
int main(){
fta_fat();
int t;
cin>>t;
while(t--){
int n;
cin>>n;
int arr[n];
loop(0,n){
cin>>arr[i];
}
int dp[n+1];
loop(0,n+1){dp[i]=-1;}
cout<<solve(arr,n,dp)<<endl;
}
return 0;
}
Second solution gives TLE:
using namespace std;
typedef long long ll;
#define v vector<ll>
#define vvi vector<vector<ll>>
const ll MOD = 1000000007;
#define fta_fat() {ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);}
#define loop(st,end) for(int i=st;i<end;i++)
#define revloop(st,end) for(int i=st;i>=end;i--)
#define pb emplace_back
int solve(int arr[],int n,int dp[]){
if(n<=0){
return 0;
}
if(n<=1){
return abs(arr[n-1]);
}
if(dp[n] !=-1){
return dp[n];
}
int ans=arr[0],ans1=arr[1];
while(arr[1]-2>0){
ans -=1;
ans1 -=2;
}
return dp[n]=min((abs(ans)+abs(ans1)+(solve(arr+2,n-2,dp))),(abs(arr[0])+(solve(arr+1,n-1,dp))));
}
int main(){
fta_fat();
int t;
cin>>t;
while(t--){
int n;
cin>>n;
int arr[n];
loop(0,n){
cin>>arr[i];
}
int dp[n+1];
loop(0,n+1){dp[i]=-1;}
cout<<solve(arr,n,dp)<<endl;
}
return 0;
}