I have solved this question using 2D recurrence relation(DP) .I have solved few such problems in past which had both 2D and 1D soln But i am not able to figure out proper 1D recurrence relation (DP) for this problem.Please help me 
.
I have solved this question using 2D recurrence relation(DP) .I have solved few such problems in past which had both 2D and 1D soln But i am not able to figure out proper 1D recurrence relation (DP) for this problem.Please help me .