本文共 595 字，大约阅读时间需要 1 分钟。

区间dp：dp[L][R] 枚举L，枚举R，枚举划分，O(N^3)，超时

状态压缩，字符串往往和起始点无关，

class Solution {public:    int countSubstrings(string s) {        int N = s.length();        int dp[N+1]; // dp[R] [0,R];        int flag[N+1][N+1]; // flag[L][R];        memset(dp,0,sizeof(dp));        memset(flag,0,sizeof(flag));        for(int r=0;r
   
    =0;l--){                if(l+1 > r-1 && s[r] == s[l]) flag[l][r] = 1;                else if(flag[l+1][r-1] && s[r] == s[l]) flag[l][r] = 1;                dp[r] += flag[l][r];            }        }        int ans = 0;        for(int i=0;i
   

转载地址：http://diwji.baihongyu.com/