I'm new to Dynamic Programming and before this, I used to solve most of the problems using recursion(if needed).
But, I'm unable to convert my
recursive code to
For eg, below is the pseudo-code for
Finding longest common-subsequence in 2 strings :
int LCS(i,j): if A[i]=='\0' or B[j]=='\0': return 0; else if(A[i]==B[j]): return 1 + LCS(i+1,j+1) else: return max(LCS(i+1,j),LCS(i,j+1))
Now, I understand the above code and below is its DP equivalent:
//Some initializations are needed which have been skipped if(A[i]=B[j]): LCS[i,j] = 1 + LCS[i-1,j-1] else: LCS[i,j] = max(LCS[i+1,j],LCS[i,j+1])
I'm not able to figure out how did they construct its DP equivalent with the help of the recursion technique?
In the recursion technique,
1 + LCS(i+1,j+1) is written whereas, in DP
1 + LCS[i-1,j-1] has been used.
I am wondering how did they use
minus in place of
plus and how will I figure out myself(for other programs involving DP) that such adjustments need to be made in the code?