Technique for converting recursive DP to iterative DP

Question

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 DP code.

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?

Answer 1

This DP code is the bottom up solution of the problem. The key is that you start with smaller subproblems and then use these solutions to solve a bigger subproblem.

The data structure we use to store these results is actually holding results to different subproblems of the problem. For eg. let say we want to find a LCS for strings abcbdab and bacdba and let the data structure be a 2D array called cache[][].

The smallest problem is when first string has only a and second string has only b. Here nothing is common. So the LCS has a length of 0 and hence $cache[1][1] = 0$ (1-based indexing). A slightly bigger problem than this would be when first string is a and second string is ba. Here the characters match and hence $cache[1][2] = 1$.

So in this way you can see we can keep growing the problem incrementally and use the previous solutions to have a solution of a bigger size problem.

The reason why we are using minus is because we are just using solutions of subproblems of smaller size represented by smaller indexes in our solution array.

You should not relate recursive and bottom up solutions. There is no direct relation. They are totally different way to solve the same problem. Hence you should keep in mind that you have to solve smaller subproblems and store their results.

I hope this clears the doubt.

Answer 2

You can easily make it fast using memoization! The problem is that you do many repetitive recursive calls. Try to first make a global dictionary/map/hashmap that maps dp[i][j] = lcs(i,j) and before every recursive call, you check if you already computed it or not.

Once that's done, you can make it DP if you want to, you're not far away.

Then you just "manually run the recursive calls" bottom-up, something like:

for i, j in enumeration(n):
    dp[i][j] = 1 + dp[i-1,j-1] if i == j else max(dp[i+1,j], dp[i,j+1])
return dp[n][n]

That's at least the gist of it!