c - 回文分区问题中此 DP 数组的基本情况 dp[0] = -1 的目的是什么？

Question

最近我在 https://leetcode.com/problems/palindrome-partitioning-ii/ 上遇到了这个问题:

给定一个字符串s，划分s使得划分的每个子串都是回文。

返回对 s 进行回文分割所需的最小切割。

Example:

Input: "aab"
Output: 1
Explanation: The palindrome partitioning ["aa","b"] could be produced using 1 cut.

这是我在互联网上发现的 C 解决方案。我一直试图了解 DP 数组在跟踪什么，我发现在 dp[j] 处，存储了回文分区的数量在 j字符串的第 th 个字符。所以dp[1]存储一个字母元素需要的分区数，它永远是0，dp[2]是strig的前两个字母.

我不明白的是，为什么我们要初始化dp[0] = -1？这似乎有点不直观，我想不出发生这种情况的原因。

int _min(int a, int b) {
    return a < b ? a : b;
}
int minCut(char* s) {
    int *dp, n, i, k;

    n = strlen(s);

    dp = malloc((n + 1) * sizeof(int));     // number of cuts on length
    //assert(dp);

    dp[0] = -1;
    for (i = 0; i < n; i ++) {
        dp[i + 1] = dp[i] + 1;
    }

    for (i = 0; i < n; i ++) {
        dp[i + 1] = _min(dp[i + 1], dp[i] + 1);

        for (k = 1;                 // "aba"
             i - k >= 0 &&
             i + k < n &&
             s[i - k] == s[i + k];
             k ++) {
            dp[i + k + 1] = _min(dp[i + k + 1], dp[i - k] + 1);
        }

        for (k = 1;                 // "aaaa"
             i - k + 1 >= 0 &&
             i + k < n &&
             s[i - k + 1] == s[i + k];
             k ++) {
            dp[i + k + 1] = _min(dp[i + k + 1], dp[i - k + 1] + 1);
        }
    }

    i = dp[n];

    free(dp);

    return i;
}

我已经用这个函数做了一些追踪，但似乎仍然找不到答案:这是我尝试 minCut("aba") 的地方，在第二次迭代的每个迭代开始时打印 i 和 dp包装 for 循环，以及 k 当它出现在第一个嵌套 for 循环中时。

i = 0
dp = [-1, 0, 1, 2]
i = 1
dp = [-1, 0, 1, 2]
k = 1
i = 2
dp = [-1, 0, 1, 0]

当我们来到元素 'b' 时，通过向前和向后展开，我们发现 "aba" 是一个回文。然后，用这个:dp[i + k + 1] = _min(dp[i + k + 1], dp[i - k] + 1);，我们得到 dp [3] = _min(dp[3], dp[1 - 1] + 1) = _min(2, -1 + 1) = 0。

令人困惑的是为什么基本情况是 dp[0] = -1，以及它如何影响 _min(dp[3], dp[0] + 1)。基本上我们要回到没有检测到回文的地方并取该值 + 1。但是为什么 minCut("") = -1？

我已经尝试解决这个问题 2.5 小时了，但我仍然无法解决。

Answer 1

这是一个保护值。当我们不想写额外的 if 时，我们会使用这样的东西，然后我们将一些 guard 元素附加到数据中，例如我们可以使用 (n+2)*(n+2) 矩阵代替 n*n 矩阵，在守卫位置上使用一些方便的值，通常为零。

请注意，每发现一个下一个回文，您就需要再进行一次切割。这是通过 + 1 在更新 dp 时实现的。但是当你发现第一个回文时，你不需要为它做切割。这与棒切割相同，将一根棒切割成一 block 你根本不需要切割它。

顺便说一句，如果 s 的长度为零，程序将返回错误的 -1。

顺便说一句，如果输入的字符串看起来像aaa...aaa，这个程序会花费很多时间来运行。基本上，它是 O(n^2)。