【动态规划】字串中回文的个数

一、题目描述

给你一个字符串 s ，请你统计并返回这个字符串中 回文子串 的数目。

注：

1. 回文字符串 是正着读和倒过来读一样的字符串。
2. 子字符串 是字符串中的由连续字符组成的一个序列。
3. 具有不同开始位置或结束位置的子串，即使是由相同的字符组成，也会被视作不同的子串。

示例：

二、思路

我们使用动态规划的方式解决这个问题，那么我们需要思考以下几个问题：

1. dp[][] 数组的含义？

dp[][] 数组表示 [i, j] 范围（j >= i）的字串是否是回文字串

2. 状态转移方程是什么？

dp[i][j] 是否是回文字串与两个状态有关，这两个状态分别是：

1） i ， j 处的字符是否相等
2） 去掉头尾 i， j 字符的子字符串是否是回文

以 字符串 abcc 为例，请看图解：

根据这个我们就可以写出状态转移方程为：

dp[i][j] = (s.charAt(i) == s.charAt(j)) && dp[i+1][j-1]
1

3. 如何初始化 dp 数组？
dp 数组直接初始化全部为 false 即可

三、代码

class Solution {
    public int countSubstrings(String s) {
        boolean[][] dp = new boolean[s.length()][s.length()];
        int res = 0;
        for(int i=s.length()-1; i>=0; i--){
            for(int j=i; j<s.length(); j++){
                if(s.charAt(i) == s.charAt(j)){
                    if(j-i<=2 || dp[i+1][j-1]){
                        res++;
                        dp[i][j] = true;
                    }
                } else{
                    dp[i][j] = false;
                }
            }
        }
        return res;                                                                                                                                                                   
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19