I have seen a lot of codes for this problem on the internet. However, I am unable to understand how the matrix is being filled while computing the DP array.
I have understood that for a string S, S[i,j] will be a palindrome if S[i] == S[j] and S[i+1], S[j-1] is also a palindrome. The base case would be that S[i,i] will always be a palindrome.
So basically, what I have done is that
for i = 0 to n:
dp[i][i] = 1
for i = 0 to n:
for j = i+1 to n:
if dp[i+1][j-1] == 1 and s[i] == s[j]:
dp[i][j] = 1
However, when I tried it for the string “aaaaa”, I could see that I got 14 instead of 15 because when trying to compute for S[0,4] i.e dp[0][4], I got 0 as the answer instead of 1 since dp[1][3] was not filled yet which should have been computed before calculating dp[0][4]…Also, in the codes I saw on the net, I could see that they were filling the matrix column wise rather than row wise. I didn’t understand why we were doing that.
Can someone help?
UPDATE - From what I can understand, I think that since we need to find the lower left diagonal element for each cell before finding the value of that cell, we go about filling the matrix columnise. Is this conclusion correct? If yes, then do we follow the same procedure for every dp problem where the answer for the (i,j) cell is derived lower diagonal elements i.e (I+1,j-1 ) and/or (I+1,j+1)?