Минимальное количество повторений в объединенном массиве символов

Question

Предположим, у меня есть два массива, и я хочу объединить их, чтобы объединенный массив имел минимальное количество повторений .Например, [ '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' ]

Я пытаюсь связать эту проблему с популярными проблемами динамического программирования, чтобы помочь мнеиз.Есть ли похожие проблемы, на которые мне стоит обратить внимание?

Answer 1

Я определяю следующую функцию: F (d, i, j) = минимальное количество возможных повторений для строки, состоящей из префикса arr1 длины i и префикса arr2 длины jза которым следует i-й (d = 0) или j-й (d = 1) символ из arr[d].Таким образом, F (d, i, j) соответствует строке длины i + j + 1.

Если вы знакомы с тем, как вычисляется расстояние Левенштейна, думайте о нем, как о том, что вместо присвоения баллов вершинамиз сетки мы назначаем оценки краям, где 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;
}