Technique for converting recursive DP to iterative DP

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?

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.

StackExchange Computer Science Q#102340, answer score: 2