Doubt over the index value used in dynamic programming
The code there is not optimal in terms of space as you can reduce the space complexity to n.

In any case I would recommend thinking as follows when you are trying to convert a brute force recursive solution to dynamic programming. 

First look at the recurrence.

f(i,j) = 1                                   if i==j
f(i,j) = f(i+1,j) + f(i,j-1) +1              if str[i] == str[j)
f(i,j) = f(i+1,j) + f(i,j-1) - f(i+1,j-1)    otherwise


Here each i,j pair is a 'state' and each state depends on other states. Dynamic programming stores previously computed states into an array/hashmap/whatever hence allowing us to reuse previously computed states to make the program run faster.

If we are using a 2d array to store the states then state (i,j) is stored in dp[i][j]. State  (i-1,j) is stored in dp[i-1][j] and so on.

In any case look at the recurrence relation of the brute force solution. You can see that:


For any given state, i depends on the values of i+1 and i
For any given state, j depends on the values of j and j-1


Thus we can make the following inference:


Since i depends on i, i+1 values, i+1 must be filled before i. Hence i loops from n to 0.
Since j depends on j, j-1 values, j-1 must be filled before j. Hence j loops from 0 to n.


So we know the direction of our loops and we can just fill in values accordingly like so:

private int count(String s) {
    int[][] dp = new int [s.length()+1][s.length()+1];
    for(int i=s.length()-1; i&gt;=0; i--) {
        for(int j = i; j&lt;s.length(); j++) {
            if(i==j)
                dp[i][j] = 1;
            else if(s.charAt(i) == s.charAt(j))
                dp[i][j] = dp[i+1][j] + dp[i][j-1] +1;
            else
                dp[i][j] = dp[i+1][j] + dp[i][j-1] - dp[i+1][j-1];
        }
    }
    return dp[0][s.length()-1];
}


And this is basically what is in the link that you posted. f(i, string.length-1)'s state contains the result which is why we return  dp[0][s.length()-1].

Time complexity: n^2; Space complexity: n^2


However this is not optimal. Optimal solution below:

Like I mentioned earlier we can make an optimization in terms of space to give us a better solution. This is not done in the link that you posted.


Notice that i depends on values of only i and i+1. This means states containing i+2, i+3, ... i+n is useless.
Similarly j depends on values of only j and j-1. This means states containing j-2, j-3, ... j-j is useless.


If something like this happens for any parameter of the recurrence, it means that we can reduce the dimension of the array by 1. We can either reduce the dimension i or we can reduce the dimension j (since either i or j can be reduced). Just make sure that the dimension you are reducing is the outer loop.

Here i represents the rows and j represents the columns of the array. Below I will show you how to reduce the i dimension. You can do the same with j but just make sure that if you reduce j, j is in the outer loop.

We are reducing dimension i, we need only 2 rows: row i and row 1+1. We dont need the other rows in the matrix. So let row 1 be row1, let row i+1 be row2.

private int count2(String s) {
    int[] row1 = new int[s.length()+1];
    int[] row2 = new int[s.length()+1];

    for(int i=s.length()-1; i&gt;=0; i--) {
        for(int j = i; j&lt;s.length(); j++) {
            if(i==j)
                row1[j] = 1;
            else if(s.charAt(i) == s.charAt(j))
                row1[j] = row2[j] + row1[j-1] + 1;
            else
                row1[j] = row2[j] + row1[j-1] - row2[j-1];
        }
        // copy row1 into row2
        for(int j=0; j&lt;row1.length; j++)
            row2[j] = row1[j];
    }
    return row1[s.length()-1];
}


The time/space analysis is:

Time complexity: n^2; Space complexity: n


So the general pattern to convert recursion to bottom up dp is:


Look at the recurrence relation
Figure out the order of the loops
Check to see if any variable x depends on x+-c where c is a constant. If that is the case, we can reduce the space complexity
Compute and store state i,j using previously computed states (unless it is the base case)
Return the result.


Hope this helps.