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>=0; i--) { for(int j = i; j<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>=0; i--) { for(int j = i; j<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<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:

1. Look at the recurrence relation
2. Figure out the order of the loops
3. 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
4. Compute and store state i,j using previously computed states (unless it is the base case)
5. Return the result.

Hope this helps.

In the above code snippet,

if(str[i] == str[k]) cps[i][k] = cps[i][k-1] + cps[i+1][k] + 1; 

whereas in the code for brute force approach the same thing works using:

Else if (str[i] == str[j]) return countPS(i+1, j) + countPS(i, j-1) + 1; 

Your usage of the concept "brute force approach" is dubious at best if not simply wrong. The analysis in initial section of the article is the standard integral part of dynamic programming for the current problem. Henceforth, I will use "in the initial analysis" instead of "for the brute force approach".

Note that the countPS(i,j) in the initial analysis is the same as cps[i,j] (or dp[i][j] in the Java version) for the dynamic programming. Both numbers means the number of palindromic subsequences the index of whose first element should be equal to or larger than $i$ and the index of whose last element should be equal or to less than $j$. That article is so brief that it does not even state this critical definition!

Let us start from the code in the initial analysis. Let us replace j with k. We get

 Else if (str[i] == str[k]) return countPS(i+1, k) + countPS(i, k-1) + 1; 

Now replacing countPS by cps, we get

 Else if (str[i] == str[k]) return cps(i+1, k) + cps(i, k-1) + 1; 

Note that the last express is none other than cps[i][k-1] + cps[i+1][k] + 1, as in the code for the dynamic programming.

in the brute-force approach if we are computing for countPS(i,j) then for str[i]==str[j] case, we need to compute countPS(i+1,j) and countPS(i,j-1) which in on translating to DP approach should mean that we need to compute cps[i-1][j] and cps[i][j+1].

Since countPS is cps, on translating to DP approach we need to compute cps[i+1][j] and cps[i][j-1] for cps[i][j]. It is as simple as that.

---

Since I'm using the bottom-up approach, I need to first find the lower array values and then find the higher ones.

Finding the lower array values might not be appropriate in some cases.

The better statement should be to first find the known or easier cases and then compute the unknown or harder one, repeatedly. Or first find the cases on the right side of the recurrence relations and then compute the cases on the left side of the recurrence, which are dependent on the former cases.

I find it really difficult as to how to move over the dp matrix when writing code for dynamic programming. Here, we traversed in a diagonal manner whereas in other examples(the one I linked in my first comment) we traverse row-wise. How do I know whether to traverse diagonally or to traverse row-wise?

Let us check how we will compute the small subproblems and then combine them to solve bigger subproblems.

First we know as base cases, all cps[0][0], cps[1][1], cps[2][2], ..., cps[n-1][n-1] are 1. Note that case cps[n-1][n-1] has largest array indices, but it is still a base case and it is considered a smaller subproblem. Their j - i = 0.

Next we will compute cps[0][1], cps[1][2], cps[2][3],..., cps[n-2][n-1], which are dependent on previous values. Their j - i = 1.

Next we will compute cps[0][2], cps[1][3],cps[2][3], ..., cps[n-3][n-1], which are dependent on previous values. Their j - i = 2.

And so on and on.

Finally we will compute cps[0][n-1], which is the biggest subproblem. Its j - i = n - 1.

Graphically, we can fill the whole table if we proceed diagonally as shown below.

* * * * * * * * * * * * * * * * * * * * * * -> * * -> * * * -> ... -> * * * * * * * * * * * * * * 

Looking at the recurrence relations, we see that we are going from cases with smaller difference of the last possible position to the first possible position to cases with larger difference. This "difference" implies "diagonal".

At this example, we are going from cases with smaller sum of indices to cases with bigger sums. This "sum" implies the other "diagonal".

Beside row-wise, column-wise, diagonal-wise, the-other-diagonal-wise, there can be tree-depth-wise or anything-wise. Which-wise depends on how the recurrence relation looks like, although row-wise or column-wise are easier to understand and implement.

---

In case you want to study how we can obtain those recurrence relations, you may take a look at this page on Stackoverflow.