DP - String

Step1, Defined a suitable table for DP problem

Similar to other DP problems, we are used to have a table for storing the temp solutions.

For example 2 strings comparation problems

ex. #583 Delete Operation for Two Strings, #72 Edit Distance

2D table is suitable for those cases.

int[][] dp = new int[s1.length+1][s2.length+1];
//the dp[i][j] means the answer for s1[:i](s1.substring(0,i)), s2[:j]

Step 2, List the basic base and fill the table in, it usually happen in the edge of table

Take #583 as example:

• i = 0, j = 0 : dp[i][j] shall be 0, means both s1 and s2 are empty

• i = 0 , j != 0 : dp[0][j] shall be j

• i !=0, j =0 : dp[i][0] shall be i

        for(int i = 0; i <= s1.length; i++){
            dp[i][0] = i;
        }
        
        for(int j = 0; j <= s2.length; j++){
            dp[0][j] = j;
        }

Step 3, fill in the other cells of the table by considering 2 possibiliies

• s1[i] == s2[j]

• s1[i] != s2[j]

for( int i = 1; i <= m; i++){
	for( int j = 1; j <= n; j++){
		if(s1[i - 1] == s2[j - 1]){
			/* Your code */
		}
		else{
			/* Your code */
		}
	}
}

The answer is dp[s1.length][s2.length]

If you are given only one string, the template will be modified as below:

The basic concept for this template is to enumerate all substring cases

int[][] dp = new int[][];
//or
boolean[][] dp = new boolean[][];

for(int dist = 1; dist < n; dist++){
    for(int i = 0; i + dist < n; i++){
        int j = dist + i;
        if(s[i] == s[j]){
            //...
        }
        else{
        
        }
    } 
}