Struggling to understand the thought process required to come up with some recurrences for Dynamic Programming problems
I was doing a few dynamic programming problems and I am struggling to understand the thought process required to come up with recurrences.
The first problem I solved was longest palindromic substring and I managed to solve it successfully using the following logic: I have a function f(i,j) which returns the longest palindromic substring between characters at positions i,j in the string. I came up with the following recurrence:
f(i,j) = true // if(s[i] = s[j]) f(i,j) = true // if(i>j) f(i,j) = true // if(s[i] = s[j] and f(i+1, j-1) == true) f(i,j) = false // otherwise
Using this recurrence I managed to solve the problem successfully.
The second problem I wanted to solve was Longest valid parentheses (which I want to do using DP not stacks). The question is: Given a string containing just the characters '(' and ')', find the length of the longest valid parentheses substring.
My initial thought process was that this was similar to the longest palindromic substring problem that I already solved. So I defined f(i,j) as a function that returns longest valid parenthesis between elements i,j. 603
The recurrence I came up with is as follows - here I use -1 to indicate that f(i,j) does not form a valid parenthesis:
f(i,j) = -1 // if i == j f(i,j) = -1 // if j=i+1 and ! (s[i] = '(' and s[j] = ')') f(i,j) = 2 // if j = i+1 and s[i] = '(' and s[j] = ')' f(i,j) = 2 + f(i+1, j-1) if s[i] = '(' and s[j] = ')' and f(i+1, j-1) > 0; f(i,j) = -1 // otherwise
My code (written in java) for the top-down version of the above is (note: dp[][] was initialized to -2 indicating state i,j is not processed yet):
private int topDown(String s, int i, int j, int[][] dp) {
if(dp[i][j] != -2)
return dp[i][j];
if(i == j)
dp[i][j] = -1;
else if(j == i+1 && (s.charAt(i) != '(' || s.charAt(j) != ')' ) )
dp[i][j] = -1;
else if(j == i+1 && (s.charAt(i) == '(' && s.charAt(j) == ')' ) )
dp[i][j] = 2;
else if(s.charAt(i) == '(' && s.charAt(j) == ')' && topDown(s, i+1, j-1, dp) > -1)
dp[i][j] = 2 + topDown(s, i+1, j-1, dp);
else
dp[i][j] = -1;
return dp[i][j];
}
This does not work for inputs like ()() as it will return 2 instead of 4.
I was unable to come up with a solution of my own so I looked it up online. I found a solution here.
In this case the author defines f(i) as the length of the longest longest valid, balanced parentheses substring which begins at index i. He then describes the recurrence as follows:
f(i) = 2 + f(i+2) // if s[i] = "(" and s[i+1] = ")" f(i) = f(i+1) + f(i + f(i+1) + 2) // s[i]="(" AND s[i+1]="(" AND s[i+f(i+1)+1]=")" f(i) = 0 // otherwise
I have not written/tested the code for the recurrence but I assume it is correct.
My questions are as follows:
1. When I was solving the problem initially I had not thought of writing it as a function of f(i). 953