The program is giving correct output for recursive relation but when i include dp array , its giveing output as 0.
Recursive code correct but dp code wrong
@akshatkaush, you can’t initialize dp matrix like this , ie.dp[1000][1000]={-1}, this initialization only works in case you initialize with zero only , so use a nested for loop to initialize your dp matrix with -1
corrected code :-
In case of any doubt feel free to ask 
Mark your doubt as RESOLVED if you got the answer