假设我有两个数组,我想合并它们,以便合并的数组具有最小的重复次数。例如[ 'x', 'x' ]
是重复。
arr1 = [ 'x', 'd', 'd', 'm', 'f', 'm' ]
arr2 = [ 'd', 'd', 'x', 'f', 'f', 'm' ]
唯一的条件是在合并数组中,来自arr1
和arr2
的元素必须以arr1
和arr2
中的各自顺序出现。下面是在保持此条件的同时重复0次的合并数组的示例。
merged = [ 'd', 'x', 'd', 'x', 'd', 'f', 'd', 'm', 'f', 'm', 'f', 'm' ]
我试图将此问题与流行的动态编程问题联系起来以帮助我解决问题。我有什么类似的问题需要研究吗?
我定义了以下函数:F(d,i,j)=由长度为i的arr1
前缀和长度为j的arr2
前缀组成的字符串可能的最小重复次数,后跟第i个(d = 0)或者来自arr[d]
的第j个(d = 1)符号。因此,F(d,i,j)对应于长度为i + j + 1的字符串。
如果您熟悉Levenshtein距离的计算方法,请将其视为不是将分数分配给网格的顶点,而是将分数分配给边,其中d
表示它是水平边还是垂直边。这给了我们一个符号“记忆”,所以我们可以检测到重复。
以下C ++代码计算最小重复次数并在二次时间内打印相应的字符串:
#include <string.h>
#include <stdio.h>
#include <algorithm>
#include <limits.h>
char A[32], B[32], C[64];
int score[2][32][32];
void print_result(int d, int i, int j)
{
char c = d ? B[j] : A[i];
int s0 = i > 0 ? score[0][i-1][j] + (A[i-1] == c) : INT_MAX;
int s1 = j > 0 ? score[1][i][j-1] + (B[j-1] == c) : INT_MAX;
if(s0 <= s1 && i > 0)
print_result(0, i-1, j);
else if(j > 0)
print_result(1, i, j-1);
printf("%c", c);
}
void print_result(int i, int j)
{
if(score[0][i-1][j] < score[1][i][j-1])
print_result(0, i-1, j);
else
print_result(1, i, j-1);
}
int main()
{
fgets(A, sizeof(A), stdin);
fgets(B, sizeof(B), stdin);
int m = strlen(A) - 1; // -1 to remove LF
int n = strlen(B) - 1;
for(int j = 0; j <= n; ++j)
{
for(int i = 0; i <= m; ++i)
{
score[0][i][j] = !i && !j ? 0 : std::min(
i > 0 ? score[0][i-1][j] + (A[i-1] == A[i]) : INT_MAX,
j > 0 ? score[1][i][j-1] + (B[j-1] == A[i]) : INT_MAX
);
score[1][i][j] = !i && !j ? 0 : std::min(
i > 0 ? score[0][i-1][j] + (A[i-1] == B[j]) : INT_MAX,
j > 0 ? score[1][i][j-1] + (B[j-1] == B[j]) : INT_MAX
);
}
}
printf("repetitions: %d\n", std::min(score[0][m-1][n], score[1][m][n-1]));
print_result(m, n);
printf("\n");
return 0;
}