时间戳

首页 > 解决方案 > 在回文分区问题中，这个 DP 数组的基本情况 dp[0] = -1 的目的是什么？

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

问题描述

最近我在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 数组正在跟踪什么，并且我发现 atdp[j]将回文分区的数量存储在j字符串的第 th 个字符处。所以dp[1]存储一个单字母元素所需的分区数，该元素始终为 0，dp[2]即字符串的前两个字母。

我不明白的是，我们为什么要初始化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") 的地方，在第二次包装 for 循环的每次迭代开始时打印 i 和 dp ，以及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]

当我们来到 element'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 小时，但我仍然无法弄清楚。

标签： carraysalgorithmdynamic-programming

解决方案

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

请注意，每发现一个回文，您就需要再剪一次。这是通过+ 1while updates来实现的dp。但是当您发现第一个回文时，您不需要对其进行切割。这与切割杆相同，将杆切割成一块，您根本不需要切割它。

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

BTW2，如果输入字符串看起来像aaa...aaa. 基本上，它是O(n^2)。

推荐阅读