Problem link: https://leetcode.com/problems/visit-array-positions-to-maximize-score/ Doubt: I tried with recursive dp but only 711/744 testcases passed. My code:
class Solution { public:
long long fun (int index,int r,long long score2,vector<int>&nums,int n,vector<long long>&dp) { if(index == n) { return 0; } if(dp[index]!=-1e12) { return dp[index]; } long long y = score2; long long start_score = score2; for(int i = index + 1;i<n;i++) { long long temp1 = score2 + fun(i,r,nums[i],nums,n,dp); if((nums[i]%2LL)!=(nums[index]%2LL)) { temp1-=r; } start_score = max(start_score,temp1); } dp[index] = start_score; return dp[index]; } long long maxScore(vector<int>& nums, int x) { int n = nums.size(); vector<int>temp; temp.push_back(0); vector<long long>dp(n); for(int i = 0;i<n;i++) { dp[i] = -1e12; } return fun(0,x,nums[0],nums,n,dp); //return dp[0]; }
};