Introduction to Dynamic Planning II (5.647.62)

One . Longest text substring

1. Construct an array dp[ len ][ len ],dp[ x ][ y ] Representation string s from x To y Whether this character is a palindrome substring

2. Assign initial value to ,i from 0 To len - 1 Give Way dp[ i ][ i ] All for 1, Because a single character also belongs to palindrome substring .

3. State transition equation ： from x To y If this string is a palindrome string, the premise is s[ x ] == s[ y ], And x + 1 To y - 1 This paragraph must also be a palindrome string . So there is dp[ x ][ y ] = (dp[x + 1][y - 1] && s[ x ] == s[ y ]).（y - x > 2）

Be careful ： You need to traverse every possible segment of the entire string （ The time complexity is n^2）. For traversal maxlen Record the longest substring length ,beginindex Record the first character position of the longest string .c Language has no function to cut strings , It is troublesome to return the answer .

char * longestPalindrome(char * s){
    int maxlen = 1, beginindex = 0, i, j, len;
    len = strlen(s);
    if(len < 2){
        return s;
    }
    int dp[len][len];
    for(i = 0; i < len; i++){
    	dp[i][i] = true; 
	}
    for(i = 0; i < len; i++){
    	for(j = 0; j <= i; j++){
    		if (s[i] != s[j]) {
                dp[j][i] = false;
            }
            else {
                if (i - j < 3) {
                    dp[j][i] = true;
                }
                else {
                    dp[j][i] = dp[j + 1][i - 1];
                }
            }
			if (dp[j][i] && i - j + 1 > maxlen) {
        		maxlen = i - j + 1;
        		beginindex = j;
			}
		}
	}
	s[beginindex + maxlen] = '\0';
	s = &s[beginindex];
	return s;
}

Two . Palindrome string

         This question is similar to finding the longest palindrome substring , The difference is that the longest string is not recorded , Counter required count, Every time I find a palindrome string count++ that will do

int countSubstrings(char * s){
    int count = 0;
    int len, i, j;
    len = strlen(s);
    int dp[len][len];
    for(i = 0; i < len; i++){
        dp[i][i] = 1;
    }
    for(i = 0; i < len; i++){
        for(j = 0; j <= i; j++){
            if(s[i] != s[j]){
                dp[j][i] = 0;
            }
            else{
                if(i - j <= 2){
                    dp[j][i] = 1;
                }
                else{
                    dp[j][i] = dp[j + 1][i - 1];
                }
                if(dp[j][i] == 1){
                    count++;
                }
            }
        }
    }
    return count;
}

3、 ... and . Different paths

1. Construct an array dp[ m ][ n ],dp[ x ][ y ] Said go x,y There are several ways to move the position .

2. Assign initial value to , Let the first row and the first column of the array be equal to 1.

3. State transition equation ： Easy to get dp[ x ][ y ] = dp[ x ][ y - 1] + dp[ x - 1][ y ].

int uniquePaths(int m, int n) {
    int dp[m][n];
    for (int i = 0; i < m; ++i) {
        dp[i][0] = 1;
    }
    for (int j = 0; j < n; ++j) {
        dp[0][j] = 1;
    }
    for (int i = 1; i < m; ++i) {
        for (int j = 1; j < n; ++j) {
            dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
        }
    }
    return f[m - 1][n - 1];
}

         Note that there dp[ i ][ j ] The value of is only related to its previous line and its previous value in the same line , So you can use a scrolling array , Let the space complexity change from m*n Down to min(m, n).

int uniquePaths(int m, int n){
    int dp[n];
    for(int i = 0; i < n; i++){
        dp[i] = 1;
    }
    for(int i = 1; i < m; i++){
        dp[0] = 1;
        for(int j = 1; j < n; j++){
            dp[j] = dp[j] + dp[j-1];
        }
    }
    return dp[n-1];
}