动态规划入门二（5.647.62）

一.最长回文子串

1.构造数组dp[ len ][ len ]，dp[ x ][ y ]表示字符串s从x到y这段字符是否是回文子串

2.赋初值，i从0到 len - 1让dp[ i ][ i ]都为1，因为单个字符也属于回文子串。

3.状态转移方程：从x到y这段字符串要是回文串的前提是s[ x ] == s[ y ]，且x + 1到y - 1这段也得是回文串。因此有 dp[ x ][ y ] = (dp[x + 1][y - 1] && s[ x ] == s[ y ])。（y - x > 2）

注意：需要让遍历整个字符串可能的每一段（时间复杂度为n^2）。遍历时用maxlen记录最长的子串长度，beginindex记录最长字串出现的首字符位置。c语言没有切割字符串的函数，返回答案较麻烦。

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;
}

二.回文子串

        此题与寻找最长回文子串相似，不同之处在于不用记录最长字串，需要用计数器count，每次找到一个回文串就count++即可

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;
}

三.不同路径

1.构造数组dp[ m ][ n ]，dp[ x ][ y ]表示走到x，y位置有几种走法。

2.赋初值，让数组的第一行和第一列都等于1。

3.状态转移方程：容易得到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];
}

        注意这里dp[ i ][ j ]的值只与其上一行以及其同一行的前一个值有关，所以可以利用滚动数组，让空间复杂度从m*n降低到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];
}