这是我参与更文挑战的第 12 天，活动详情查看：更文挑战

区间 DP

有一类 DP 题目，看起来像是一个线性的数组，但是如果仔细分析，就会发现要处理的却是一个一个的子区间。下面我们依然通过一道例题，使用 6 步破题法进行求解。

例子：扰乱字符串

题目

【题目】使用下面描述的算法可以扰乱字符串 s 得到字符串 t 。

Step 1. 如果字符串的长度为 1 ，算法停止。

Step 2. 如果字符串的长度 > 1 ，执行下述步骤：

在一个随机下标处将字符串分割成两个非空的子字符串。即如果已知字符串 s ，则可以将其分成两个子字符串 x 和 y ，且满足 s = x + y 。

随机决定是“交换两个子字符串”还是“保持这两个子字符串的顺序不变”。即在执行这一步骤之后，s 可能是 s = x + y 或者 s = y + x 。

Step 3. 在 x 和 y 这两个子字符串上继续从 Step 1 开始递归执行此算法。

有两个长度相等的字符串 s1 和 s2，判断 s2 是否是 s1 的扰乱字符串。如果是，返回 true ；否则，返回 false 。

输入：s1 = “great”, s2 = “rgeat”

输出：true

解释：经过如下操作即可从 s1 得到 s2：

分析

【分析】当拿到这个题目的时候，我们看到 true/false，可以联想到这应该是个 DP 题的信号。因为题目也没有要求输出具体怎么操作。

因此，你可以由此想到使用 6 步破题法，而不是立马跟着题意开始切分字符串。

1. 最后一步

首先看最后一步，题目中给定两个字符串 s1，s2，那么 s1 在最后一步操作之后是否可以得到 s2 呢？（假设 s1 的长度为 N，下标从 0 开始）

我们分析一下，s1 在操作的时候，可以有以下步骤：

1）在位置 p 处进行切分，将 s1 切分为 x = [0, … p] 和 y = [p + 1, N)；

2）然后再分别处理 s1 = x + y 和 s1 = y + x 能否拼成 s2。

其中 p 的取值范围是 [0 ~ N-2]，所以一共有 N-1 种选项。

但是这样操作并不能降低处理的数据规模，无法将一个大问题切分为更多的小问题，也就是说我们只是找到了原始问题的一个等价问题。

这说明我们最后一步找得不准！需要重新思考。如果 s1 是 s2 的扰乱字符串，那么在最后一步的时候，存在以下 2 种情况（判断的时候，只需要判断对应颜色相同的部分）：

Case 1. 找到某个位置，将 s1, s2 都切成两半，其中 s1 = x + y，而 s2 = c + d，那么我们只需要保证 x 是 c 的扰乱字符串，y 是 d 的扰乱字符串。

Case 2. 找到某个位置，切分后，使得 s1 = x + y，s2 = c + d，并且 x 是 d 的扰乱字符串，而 y 是 c 的扰乱字符串。

我们发现，找准最后一步之后，原始问题的规模减小了很多。

2. 子问题

起初要求解的问题是：

判断 s1 是不是 s2 的扰乱字符串。

经过最后一步的处理之后，需要处理的问题被拆分为两种情况：

Case 1. s1 = x + y, s2 = c + d，判断 <x, c> 和 <y,d> 是不是扰乱字符串；

Case 2. s1 = x + y, s2 = c + d，判断 <x, d> 和 < y, c> 是不是扰乱字符串。

到这里，我们可以将原问题表示如下：

f(s1, s2) = true，表示 s1 是 s2 的扰乱字符串，false 则表示不是。

那么最后一步就可以表示为：

f(s1, s2) = f(x, c) && f(y, d) || f(x, d) && f(y, c)
其中 s1 = x + y, s2 = c + d

3. 递推关系式

我们可以用伪代码表示一下这个递推关系式，代码如下：

boolean isScramble(s1, s2) {
  N = len(s1)
  f(s1, s2) = false;
  for cutPos in range(0, N) {
    // 第一种切分方式
    // s1 = x + y
    x = s1[0:cutPos]
    y = s1[cutPos+1, N)
    // s2 = c + d
    c = s2[0:cutPos]
    d = s2[cutPos+1,N)
    // 看第一种是否满足条件
    f(s1,s2) = f(x,c) && f(y,d);
    if (f(s1,s2)) break;
    // 第二种切分方式
    c = s2[0:N-cutPos-1]
    d = s2[N-cutPos:N)
    // 看第二种是否满足条件 
    f(s1, s2) = f(x,d) && f(y, c);
    if (f(s1,s2)) break;
  }
}
复制代码

4. f(x) 的表示

接下来，我们需要看一下 f(s1, s2) 的表示。

如果简单一点，我们当然可以使用 HashMap<String,HashMap<String, Boolean>> 双层哈希函数来处理（难办一点，可以用 s1+”#”+s2 作为 key，然后只使用一层哈希函数）。

但是就这道题而言，我们还有更好的表达方式。观察题目可以发现：子问题里面的 <x, y> 和 <c, d> 都是原字符串的子串。

    // s1 = x + y
    x = s1[0:cutPos]
    y = s1[cutPos+1, N)
    // s2 = c + d
    c = s2[0:cutPos]
    d = s2[cutPos+1,N)
复制代码

那么可以用起始位置与终止位置来表示：

f(s1, s2) = f([s1_start, s1_end], [s2_start, s2_end])
复制代码

到这里，我们可以认为信息已经变成了 f(s1_start, s1_end, s2_start, s2_end)。针对这个 4 维的信息，可以通过建立一个 4 维数组来处理。比如：dp[s1_start][s1_end][s2_start][s2_end]。

但是，如果 s1 字符串要是 s2 字符串的扰动字符串，那么这两者的长度应该是相等的。因此，应该满足如下的关系：

s1_end – s1_start = s2_end – s2_start

也就是说，两个字符串的长度总是相等的，那么我们可以把 4 维的信息压缩为 3 维：

s1_start

s2_start

length
复制代码

因为 s1_end = s1_start + length，而 s2_end = s2_start + length。也就是说，3 维的信息与 4 维的信息完全是等价的。那么，我们可以把原来 4 维的数组 dp，更改为 3 维的数组 dp[s1_start][s2_start][length]。

5. 初始条件与边界

虽然有了第 3 步中的递推关系，但是我们很快可以发现，有那么几项需要提前处理，否则无法计算结果。

都是空字符串：s1 = empty，s2 = empty。（就本题而言，题目已给定了不会出现空字符串）。

两个字符串长度都是 1：len(s1) = 1, len(s2) = 1。

还有一些可以提前处理的操作，比如 s1 与 s2 的字符串长度不相等，这种直接可以返回 False，因为扰动字符串需要两个字符串长度相等。

6. 计算顺序

我们在初始条件中，已经处理了长度为 0（空字符串），长度为 1 的子串的情况。如果再接着走两步，那么应该再去计算长度为 2 的任意子串是不是相互为扰动字符串。然后再计算长度为 3，长度为 4，直到长度为 N 的子串。

可以肯定，当计算到长度为 N 的时候，我们就能得到最终解。

完整代码

【分析】经过了前面的 DP 分析 6 步法，现在应该可以写出如下代码了（解析在注释里）：

boolean isScramble(String s1, String s2) {
  final int s1len = s1 == null ? 0 : s1.length();
  final int s2len = s2 == null ? 0 : s2.length();
  if (s1len != slen2) {
    return false;
  }
  // N表示后面字符串的长度
  final int N = s1len;
  boolean[][][] dp = new boolean[N + 1][N + 1][N + 1];
  // 初始条件是长度为1的情况
  for (int s1start = 0; s1start < N; s1start++) {
    for (int s2start = 0; s2start < N; s2start++) {
      dp[s1start][s2start][1] = s1.charAt(s1start) == s2.charAt(s2start);
    }
  }
  // 那么再通过递推公式计算其他长度的情况
  // 子串的截取，这里我们采用开闭原则[start, end)
  // 也就是说，end是可以取到N的。
  for (int len = 2; len <= N; len++) {
    for (int s1start = 0; s1start + len <= N; s1start++) {
      for (int s2start = 0; s2start + len <= N; s2start++) {
        // 现在我们需要计算两个子串
        // X = s1[s1start, s1start+len)
        // Y = s2[s2start, s2start+len)
        // 这两个子串是否是扰动字符串
        // 那么根据递推公式，我们需要找切分点
        // 切分子串的时候
        // X 切分为 X = a + b, 分为左右两半
        // Y 切分为 Y = c + d，同样分为左右两半
        // 左边的长度为leftLen, 右边的长度就是len - leftLen
        for (int leftLen = 1; leftLen < len && !dp[s1start][s2start][len];
             leftLen++) {
          // 第一种切分，case 1
          // X = a + b, Y = c + d
          // [s1start, s1start + leftLen) <- a
          // [s2start, s2start + leftLen) <- c
          // [s1start + leftLen, s1start + len) <- b
          // [s2start + leftLen, s2start + len) <- d
          boolean c1 =
            // <a, c>
            dp[s1start][s2start][leftLen] &&
            // <b, d>
            dp[s1start + leftLen][s2start + leftLen][len - leftLen];
          // 第2种切分
          // X = a + b, Y = c + d
          // [s1start, s1start + leftLen) <- a
          // [s2start + len - leftLen, s2start + len) <- d
          // [s1start + leftLen, s1start + len) <- b
          // [s2start, s2start + len - leftLen) <- c
          boolean c2 =
            // <a, d>
            dp[s1start][s2start + len - leftLen][leftLen] &&
            // <b, c>
            dp[s1start + leftLen][s2start][len - leftLen];
          dp[s1start][s2start][len] = c1 || c2;
        }
      }
    }
  }
  return dp[0][0][N];
}
复制代码