字符串划分 dp

解码方法的状态如何定义？

• 问题: 数字字符串按 1-26 映射到字母, 求解码方案总数 (91);
• 阶段: 按前缀长度划分;
• 状态: dp[i] 为前 i 个字符的解码方案数;
• 初值: dp[0] = 1, 表示空串有一种解码方式 (乘法/累加的基准); 其余为 0;

解码方法的转移方程怎么写？

• 最后一步的两种选择:
  • 用一个字符: 当 s[i-1] !== "0" 时合法, dp[i] += dp[i-1];
  • 用两个字符: 当 i > 1、s[i-2] !== "0" 且 Number(s.slice(i-2, i)) <= 26 时合法, dp[i] += dp[i-2];
• 前导零: 0 不能单独解码, 也不能作为两位数的首位, 两个条件分别覆盖;
• 答案: dp[n];

const numDecodings = (s) => {
  const n = s.length;
  const dp = new Array(n + 1).fill(0);
  dp[0] = 1;
  for (let i = 1; i <= n; i++) {
    if (s[i - 1] !== "0") dp[i] += dp[i - 1];
    if (i > 1 && s[i - 2] !== "0" && Number(s.slice(i - 2, i)) <= 26) dp[i] += dp[i - 2];
  }
  return dp[n];
};

• 复杂度: 时间 O(n), 空间 O(n);

单词拆分怎么转化为前缀划分？

• 问题: 判断字符串能否拆成字典中的若干单词 (139);
• 状态: dp[i] 表示 s[0..i) 能否被拆分;
• 转移: 枚举切分点 j (1 <= j <= i), 若 dp[j-1] 为真且 s[j-1..i) 在字典中, 则 dp[i] 为真;
• 初值: dp[0] = true, 其余为 false;
• 答案: dp[n];

const wordBreak = (s, wordDict) => {
  const set = new Set(wordDict);
  const n = s.length;
  const dp = new Array(n + 1).fill(false);
  dp[0] = true;
  for (let i = 1; i <= n; i++) {
    for (let j = 1; j <= i; j++) {
      if (dp[j - 1] && set.has(s.slice(j - 1, i))) {
        dp[i] = true;
        break;
      }
    }
  }
  return dp[n];
};

• 复杂度: 时间 O(n^2) (字典查找按 O(1) 计), 空间 O(n);

两个问题的状态设计有什么共性？

• 共性: 都是"前 i 个字符能否/有多少种方式划分"的前缀 dp;
• 差别: 解码方法固定看 1 个或 2 个字符, 单词拆分的切分点需要枚举;
• 同类: 切分点枚举到"回文划分"时用区间 dp 判断回文, 见 回文子序列与子串;