Ответ 1

Конечно! Существует так мало возможных операций с таким количеством 0. Я имею в виду, ответ не более 200.

Взгляни на

10001010000000001
vs       ||||||
10111010100000010

Посмотрите на все нули с трубами. Неважно, какой из них вы в конечном итоге удаляете? Нету. Это ключ.

Решение 1

Рассмотрим нормальное решение n * m:

dp(int i, int j) {
    // memo & base case
    if( str1[i-1] == str1[j-1] ) {
        return dp(i-1, j-1);
    }
    return 1 + min( dp(i-1, j), dp(i-1, j-1), dp(i, j-1) );
}

Если бы почти каждый персонаж был 0, что бы заработало больше времени?

if( str1[i-1] == str1[j-1] ) { // They will be equal so many times, (99900)^2 times!
    return dp(i-1, j-1);
}

Я мог представить себе, что он обрушивается на десятки тысяч рекурсий. Все, на что вы на самом деле нуждаетесь в логике, - это 200 критических точек. Вы можете игнорировать остальные. Простая модификация

if( str1[i-1] == str1[j-1] ) {
    if( str1[i-1] == 1 )
        return dp(i-1, j-1); // Already hit a critical point

    // rightmost location of a 1 in str1 or str2, that is <= i-1
    best = binarySearch(CriticalPoints, i-1);
    return dp(best + 1, best + 1); // Use that critical point
    // Important! best+1 because we still want to compute the answer at best
    // Without it, we would skip over in a case where str1[best] is 1, and str2[best] is 0.
}

CriticalPoints будет массивом, содержащим индекс каждого 1 в str1 или str2. Убедитесь, что он отсортирован перед бинарным поиском. Имейте в виду эти гоччи. Моя логика: Хорошо мне нужно, чтобы убедиться, чтобы вычислить ответ на индекс best сам, так что давайте идти с best + 1 в качестве параметра. Но, если best == я - 1, мы застреваем в цикле. Я обработаю это с быстрой str1[i-1] == 1. Сделано, плех.

Вы можете быстро проверить правильность, отметив, что в худшем случае вы нажмете все 200 * 100000 комбинаций я и j, которые будут делать критические точки, и когда эти критические точки вызовут min(a, b, c), он будет делать только три рекурсивные вызовы функций. Если какая-либо из этих функций является критическими точками, то она является частью тех 200 * 100000, которые мы уже подсчитали, и мы можем ее игнорировать. Если это не так, то в O (log (200)) он попадает в один вызов в другой критической точке (теперь это то, что мы знаем, является частью 200 * 100000, которые мы уже подсчитали). Таким образом, каждая критическая точка занимает в худшем случае 3*log(200) время, исключая вызовы в другие критические точки. Аналогично, самый первый вызов функции попадет в критический момент времени log(200). Таким образом, мы имеем верхнюю границу O (200 * 100000 * 3 * log (200) + log (200)).

Кроме того, убедитесь, что ваша таблица заметок - это hashmap, а не массив. 10 ^ 10 памяти не поместится на вашем компьютере.

Решение 2

Вы знаете, что ответ не более 200, поэтому просто не позволяйте себе вычислять больше, чем многие операции.

dp(int i, int j) { // O(100000 * 205), sounds good to me.
    if( abs(i - j) > 205 )
        return 205; // The answer in this case is at least 205, so it irrelevant to calculating the answer because when min is called, it wont be smallest.
    // memo & base case
    if( str1[i-1] == str1[j-1] ) {
        return dp(i-1, j-1);
    }
    return 1 + min( dp(i-1, j), dp(i-1, j-1), dp(i, j-1) );
}

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

Решение 3

Как и решение 2, мы могли бы сделать это следующим образом:

dp(int i, int j, int threshold = 205) {
    if( threshold == 0 )
        return 205;
    // memo & base case
    if( str1[i-1] == str1[j-1] ) {
        return dp(i-1, j-1);
    }
    return 1 + min( dp(i-1, j, threshold - 1), dp(i-1, j-1, threshold - 1), dp(i, j-1, threshold - 1) );
}

Вы можете беспокоиться о том, что dp (i-1, j-1) стекает вниз, но порог держит я и j близко друг к другу, поэтому он вычисляет подмножество решения 2. Это происходит потому, что порог уменьшается каждый раз, когда я и j становятся дальше Кроме. dp(i-1, j-1, threshold) сделает его идентичным решению 2 (таким образом, это немного быстрее).

Космос

Эти решения дадут вам ответ очень быстро, но если вы хотите также оптимизировать пространство, было бы легко заменить str1[i] на (i in Str1CriticalPoints)? 1: 0 (i in Str1CriticalPoints)? 1: 0, используя hashmap. Это дало бы окончательное решение, которое все еще очень быстро (хотя будет медленнее на 10 раз), а также избегает сохранения длинных строк в памяти (до того момента, когда он может работать на Arduino). Я не думаю, что это необходимо.

Обратите внимание, что исходное решение не использует пробел 10 ^ 10. Вы упоминаете "еще лучше, менее 10 ^ 10 пробелов", что подразумевает, что пространство 10 ^ 10 будет приемлемым. К сожалению, даже с достаточным объемом оперативной памяти, итерация, хотя это пространство занимает 10 ^ 10 раз, что определенно неприемлемо. Ни одно из моих решений не использует пространство 10 ^ 10: только 2 * 10 ^ 5, чтобы удерживать строки, чего можно избежать, как обсуждалось выше. 10 ^ 10 Байт для 10 ГБ.

EDIT: в качестве примечаний для манифеста, вам нужно только проверить abs(i - j) > 105, так как остальные 100 вставок, необходимых для приравнивания i и j будут тянуть число операций выше 200.