输出最小数k的回文

Question

对于一个动态编程问题，我试图想出一个英文算法、备忘录表、最佳情况和递归调用来填充以下问题的表：

给定长度为n的字符串s，设计一个输出最小数字k的算法，使得s = w1w2 . . . wk，其中每个wi都是回文。换句话说，找到最小的k，使得s可以写成k个回文的串联。有关回文的定义，请参阅实践问题。例如，如果s = "add"，则算法应该输出k = 2，因为我们可以取w1 ="a"和w2 ="dd"。另一方面，如果s = "ada"，则算法应输出k=1。

我想出了以下算法：

Start
Declare variables s as string, n as integer, k as integer, i as integer.
Initialize k to 1
Read s
n<-length of string s
while  i is less then n-1
if s[i]==s[i+1] then
k++
end if
display  k
End

然而，我不确定如何生成记忆表、最佳情况以及填充该表所需的递归步骤。

Answer 1

在动态编程中，备忘录表保存实际问题的子问题的答案。结合这些子问题的答案，我们可以计算出实际问题的答案。

对于这个问题，实际的问题是为字符串s找到最小的k回文。所以，子问题可能类似于字符串s的部分/子字符串的最小k是多少。为了简化它，如果我们知道子串s[0:i]和s[i+1:length(s)-1]的答案，那么我们可以计算s[0:length(s)-1] = s[0:i] + s[i+1:length(s)-1]的答案。

由此我们可以很容易地形成我们的递归关系：

minKPalindrome(start, end) = minKPalindrome(start, i) + minKPalindrome(i+1, end), (start < i < end)
here, minKPalindrome(start, end) is function that return minimum k plaindrome for s[start:end] substring

可能的基本情况：

- if start > end , return answer 0
- s[start:end] is palindrome, so return answer is 1

递归算法：

memo[start][end] = contains answer for s[start:end]
minKPalindrome(start, end) {
if s[start:end] is palindrome {
return 1
}
if ans is already saved in memo[start][end] {
return memo[start][end]
}
memo[start][end] = end - start + 1 // set maximum possible answer
for i = start+1 to end-1 {
memo[start][end] = min( memo[start][end], minKPalindrome(start, i) + minKPalindrome(i+1, end))
}
return memo[start][end]
}

优化算法：

推广以前的递归关系：

minKPalindrome(s[start: end]) = minKPalindrome(s[start, i]) + minKPalindrome(s[i+1, end])
or,
minKPalindrome(s[start: end]) = minKPalindrome(prefix of s) + minKPalindrome(suffix of s)

我们可以只检查回文的前缀，而不是检查字符串s的每个前缀。

if start[start:i] is palindrome {
minKPalindrome(s[start: end]) = 1 + minKPalindrome(s[i+1:end])
}

基本情况：

- if start > end, return 0

递归算法：

memo[start] = contains answer for s[start:end]
end = lenght(s) - 1
minKPalindrome(start, end) {
if start > end {
return 0
}
if ans is already saved in memo[start] {
return memo[start]
}
memo[start] = end - start + 1 // set maximum possible answer
for i = start to end {
if s[start:i] is palindrome {
memo[start] = min( memo[start], 1 + minKPalindrome(i+1, end))
}
}
return memo[start]
}

迭代算法：对于迭代算法，我们将为字符串s的前缀保存答案。

memo[i] = contains answer for s[0:i]
for i = 0 to length(s)-1 {
for j= 0 to i {
if s[j:i] is palindrome {
memo[i] = min( memo[i], 1 + memo[j-1])
}
}
}