【动态规划】647. 回文子串

力扣链接：. - 力扣（LeetCode）

动规大法开始吟唱：

dp[i][j]含义：从i到j的子串是否为回文子串

递推公式：当s[i] == s[j]时

1. j-i<=1时, dp[i][j]为true

2. 否则，若dp[i+1][j-1]为true，则dp[i][j]为true

遍历顺序：dp[i][j]的状态依赖dp[i+1][j-1]，所以i从大到小，j从小到大遍历

ac代码如下：

class Solution {public int countSubstrings(String s) {int len = s.length();boolean[][] dp = new boolean[len][len];int ans = 0;for(int i=len-1;i>=0;i--){for(int j=i;j<len;j++) {if(s.charAt(i)==s.charAt(j)) {if(j-i<=1){dp[i][j]=true;ans++;} else if(dp[i+1][j-1]){dp[i][j]=true;ans++;}}}} return ans;}
}