算法刷题 DAY60

647.回文子串

int countSubstrings(char* s) {
 
    int res=0;
    int len=strlen(s);
    bool dp[len][len];
    for(int i=0;i<len;i++){
        for(int j=0;j<len;j++){
            dp[i][j]=false;
        }
    }
 
    for(int i=len-1;i>=0;i--){
        for(int j=i;j<len;j++){
 
            if(s[i]==s[j]){
                if(j-i<=1){
                    dp[i][j]=true;
                    res++;
                }
                else {
                    if(dp[i+1][j-1]==true){
                        dp[i][j]=true;
                        res++;
                    }
                }
            }
 
        }
    }
 
    return res;
    
}

516.最长回文子序列

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