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状态相比，有可能能减少时间上的计算开销，因为只计算了需要的状态，不需要使用的状态不会被计算

问题

思路

题目需要求字符串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数组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]
若上式满足，则证明正序和反序是同一个字符串，即字符串为回文串

代码

这里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];
    }
}