DP + 记忆化搜索 + 字符串HASH：回文串询问Ⅱ

迈不过友情╰ 2023-10-06 20:45 4阅读 0赞

## DP + 记忆化搜索 + 字符串HASH：回文串询问Ⅱ ##

#### 文章目录 ####

*  DP + 记忆化搜索 + 字符串HASH：回文串询问Ⅱ
 *   *   *  记忆化搜索
         *  问题
         *  思路
         *  代码

#### 记忆化搜索 ####

我们知道DP状态求解的常用写法是定义一个DP数组，然后通过状态转移方程填充这个DP数组，得到所有状态。而记忆化搜索是DP状态求解的另一种写法，原理也是把计算过的状态用一个dp数组保存，下次就可以直接调用。它是一种自顶向下的写法，从最终状态出发，去计算最终状态依赖的状态，然后以同样的方式计算最终状态依赖的状态依赖的状态（这里并没有多打一遍）。实际上就是一个递归求解的过程，可以理解为DP状态求解的递归写法。  
  拿经典的爬楼梯问题举例，每次可以爬一阶楼梯，或两阶楼梯，需要求从0阶爬到n阶的所有可能方式数目：我们用递归函数int d(int n)来计算从第0阶爬到第n阶的方式数，那么显然调用d(n)的返回值就是答案。我们同样需要定义dp\[\]数组，不过我们将dp\[\]数组初始化为-1，表示dp\[\]数组中的状态尚未计算，在递归函数中进行判断，若`dp[n] != -1`，则表示dp\[n\]已经被计算过，直接返回即可，否则依据状态转移方程进行dp\[n\]的计算，按照爬楼梯的转移方程dp\[n\]=dp\[n-1\]+dp\[n-2\]，我们可以写出递归函数：

static {
        
    	Arrays.fill(dp, -1);
    }
    
    int d(int n) {
        
    	if (n <= 1) {
        
    		return 1;
    	}
    	if (dp[n] != -1) {
        
    		return dp[n];
    	}
    	dp[n] = d(n - 1) + d(n - 2);
    	return dp[n];
    }

这就是dp的记忆化搜索写法，与求出全部dp状态相比，有可能能减少时间上的计算开销，因为只计算了需要的状态，不需要使用的状态不会被计算

#### 问题 ####

![在这里插入图片描述][watermark_type_d3F5LXplbmhlaQ_shadow_50_text_Q1NETiBA5bCP54G15a6d_size_20_color_FFFFFF_t_70_g_se_x_16]  
![在这里插入图片描述][watermark_type_d3F5LXplbmhlaQ_shadow_50_text_Q1NETiBA5bCP54G15a6d_size_20_color_FFFFFF_t_70_g_se_x_16 1]

#### 思路 ####

题目需要求字符串S内区间\[l,r\]中回文子串的数目，那么我们自然而然可以想到设DP\[l\]\[r\]为\[l,r\]区间回文子串的个数，预处理出DP数组后对每个询问直接回答即可。  
  我们来研究一下头尾元素对状态转移的影响，\[l,r\]区间去掉头尾元素对应的状态是DP\[l + 1\]\[r - 1\]，只看增加头元素之后，头元素可能会与\[l + 1,r - 1\]区间内的子串构成新回文子串，对应的状态是DP\[l\]\[r - 1\]，只看增加尾元素之后，尾元素可能会与\[l + 1,r - 1\]区间内的子串构成新回文子串，对应的状态是DP\[l + 1\]\[r\]。那么同时增加头尾元素，会造成上述两种状态影响，并且再加上可能导致整个\[l,r\]区间字符串构成回文串。根据容斥原理，我们可以得到状态转移方程：  
`DP[l][r]=DP[l+1][r]+DP[l][r-1]-DP[l+1][r-1]+(s[l ~ r]是否为回文)`  
  由于`DP[l+1][r-1]`表示的回文子串数目包含在`DP[l+1][r]`中，也包含在`DP[l][r-1]`中，因此多加了一次，需减去  
  对于判断s\[l ~ r\]是否为回文串，使用字符串HASH即可，字符串HASH原理详见：[字符串HASH][HASH]。若一个字符串为回文串，那么它的正序和反序相同，我们正着遍历字符串得到一个HASH数组hs\[\]，反着遍历得到另一个HASH数组hsR\[\]，S\[l ~ r\]若为回文串，则满足：  
`hs[r] - hs[l - 1] * baseMul[r - l + 1] == hsR[n - l + 1] - hsR[n - r] * baseMul[r - l + 1]`  
  若上式满足，则证明正序和反序是同一个字符串，即字符串为回文串  
![在这里插入图片描述][watermark_type_d3F5LXplbmhlaQ_shadow_50_text_Q1NETiBA5bCP54G15a6d_size_20_color_FFFFFF_t_70_g_se_x_16 2]

#### 代码 ####

这里DP使用记忆化搜索实现

import java.util.*;
    
    public class Main {
        
        static long[][] dp = new long[1005][1005];
        static char[] str = new char[1005];
        static long[] hs = new long[1005];
        static long[] hsR = new long[1005];
        static long base = 23333;
        static long[] baseMul = new long[1005];
        static {
        
            baseMul[0] = 1;
            for (int k = 1;k < 1005;k++) {
        
                baseMul[k] = baseMul[k - 1] * base;
            }
        }
        public static void main(String[] args) {
        
            int n, q, l, r, i;
            StringBuilder stringBuilder = new StringBuilder();
            Scanner scanner = new Scanner(System.in);
            while (scanner.hasNextInt()) {
        
                n = scanner.nextInt();
                q = scanner.nextInt();
                stringBuilder.delete(0, stringBuilder.length());
                stringBuilder.append(scanner.next());
                hs[0] = 0;
                hsR[0] = 0;
                for (i = 1;i <= n;i++) {
        
                    Arrays.fill(dp[i], -1);
                    str[i] = stringBuilder.charAt(i - 1);
                    hs[i] = hs[i - 1] * base + (stringBuilder.charAt(i - 1) - 'a' + 1);
                    hsR[i] = hsR[i - 1] * base + (stringBuilder.charAt(n - i) - 'a' + 1);
                }
                for (i = 0;i < q;i++) {
        
                    l = scanner.nextInt();
                    r = scanner.nextInt();
                    System.out.println(getDp(l, r, n));
                }
            }
        }
    
        static long getDp(int l, int r, int n) {
        
            if (l > r || l > n || r < 1) {
        
                return 0;
            }
            if (l == r) {
        
                return 1;
            }
            if (dp[l][r] != -1) {
        
                return dp[l][r];
            }
            dp[l][r] = getDp(l, r - 1, n) + getDp(l + 1, r, n) - getDp(l + 1, r - 1, n);
            if (getHash(l, r, hs) == getHash(n - r + 1, n - l + 1, hsR)) {
        
                dp[l][r]++;
            }
            return dp[l][r];
        }
    
        static long getHash(int l, int r, long[] hs) {
        
            return hs[r] - hs[l - 1] * baseMul[r - l + 1];
        }
    }

[watermark_type_d3F5LXplbmhlaQ_shadow_50_text_Q1NETiBA5bCP54G15a6d_size_20_color_FFFFFF_t_70_g_se_x_16]: https://img-blog.csdnimg.cn/56abbfd71233463e8c4ba0d06d4f2a22.png?x-oss-process=image/watermark,type_d3F5LXplbmhlaQ,shadow_50,text_Q1NETiBA5bCP54G15a6d,size_20,color_FFFFFF,t_70,g_se,x_16
[watermark_type_d3F5LXplbmhlaQ_shadow_50_text_Q1NETiBA5bCP54G15a6d_size_20_color_FFFFFF_t_70_g_se_x_16 1]: https://img-blog.csdnimg.cn/bd25ccab28854e12a3ace309ee12b844.png?x-oss-process=image/watermark,type_d3F5LXplbmhlaQ,shadow_50,text_Q1NETiBA5bCP54G15a6d,size_20,color_FFFFFF,t_70,g_se,x_16
[HASH]: https://blog.csdn.net/qq_44709990/article/details/120614450
[watermark_type_d3F5LXplbmhlaQ_shadow_50_text_Q1NETiBA5bCP54G15a6d_size_20_color_FFFFFF_t_70_g_se_x_16 2]: https://img-blog.csdnimg.cn/7ea094d5509446b0938d32c7c8d233b9.jpg?x-oss-process=image/watermark,type_d3F5LXplbmhlaQ,shadow_50,text_Q1NETiBA5bCP54G15a6d,size_20,color_FFFFFF,t_70,g_se,x_16