(复杂dp, 周赛t4)5837. 划分数字的方案数

5837. 划分数字的方案数

官方题解
关键是一些数学公式推导，使用presum和lcp（预处理的 最长公共前缀）优化时间

class Solution {
  typedef long long ll;
  const int MOD = 1e9 + 7;

 public:
  int numberOfCombinations(string num) {
    if (num[0] == '0') return 0;
    int n = num.size();
    int f[n][n], lcp[n + 1][n + 1];  // 这两个数组不能开成long long，否则会爆内存
    memset(lcp, 0, sizeof lcp);
    memset(f, 0, sizeof f);
    for (int i = n - 1; i >= 0; i--) {
      for (int j = i; j < n; j++) {
        lcp[i][j] = num[i] == num[j] ? lcp[i + 1][j + 1] + 1 : 0;
      }
    }
    for (int i = 0; i < n; i++) f[0][i] = 1;
    for (int i = 1; i < n; i++) {
      if (num[i] == '0') continue;
      ll presum = 0;
      for (int j = i; j < n; j++) {
        int len = j - i + 1;
        f[i][j] = presum;
        if (i - len >= 0) {
          if (lcp[i - len][i] >= len ||
              num[i - len + lcp[i - len][i]] <= num[i + lcp[i - len][i]]) {
            f[i][j] = (f[i][j] + f[i - len][i - 1]) % MOD;
          }
          presum = (presum + f[i - len][i - 1]) % MOD;
        }
      }
    }
    ll res = 0;
    for (int i = 0; i < n; i++) {
      res = (res + f[i][n - 1]) % MOD;
    }
    return res;
  }
};