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
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
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].
cps, on translating to DP approach we need to compute
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, cps, cps, ..., 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, cps, cps,..., cps[n-2][n-1], which are dependent on previous values. Their
j - i = 1.
Next we will compute cps, cps,cps, ..., 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[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.