Отдельные объяснения DP

Из LeetCode

Учитывая строку S и строку T, подсчитайте количество различных подпоследовательностей T в S.

Подпоследовательность строки - это новая строка, которая формируется из исходной строки путем удаления некоторых (не может быть ни одного) символов без нарушения относительного положения оставшихся символов. (то есть "ACE" является подпоследовательностью "ABCDE", а "AEC" - нет).

Вот пример: S = "Кролик", T = "Кролик"

Вернуть 3.

Я вижу очень хорошее решение для DP, но мне трудно понять, кто-нибудь может объяснить, как работает этот dp?

int numDistinct(string S, string T) {

    vector<int> f(T.size()+1);

    //set the last size to 1.
    f[T.size()]=1;

    for(int i=S.size()-1; i>=0; --i){
        for(int j=0; j<T.size(); ++j){
            f[j]+=(S[i]==T[j])*f[j+1];
            printf("%d\t", f[j] );
        }
        cout<<"\n";
    }
    return f[0];
}

Ответ 1

Сначала попробуйте решить проблему самостоятельно, чтобы придумать наивную реализацию:

Скажем, что S.length = m и T.length = n. Пусть написано S{i} для подстроки S, начиная с i. Например, если S = "abcde", S{0} = "abcde", S{4} = "e" и S{5} = "". Мы используем аналогичное определение для T.

Пусть N[i][j] - различные подпоследовательности для S{i} и T{j}. Нас интересует N[0][0] (потому что они являются полными строками).

Есть два простых случая: N[i][n] для любых i и N[m][j] для j<n. Сколько подпоследовательностей существует для "" в некоторой строке S? Точно 1. Сколько для некоторого T в ""? Только 0.

Теперь, учитывая некоторые произвольные i и j, нам нужно найти рекурсивную формулу. Есть два случая.

Если S[i] != T[j], мы знаем, что N[i][j] = N[i+1][j] (надеюсь, вы можете проверить это для себя, я хочу подробно объяснить критический алгоритм выше, а не эту наивную версию).

Если S[i] = T[j], у нас есть выбор. Мы можем либо "совместить" эти символы, либо продолжать следующие символы как S, так и T, или мы можем игнорировать совпадение (как в случае S[i] != T[j]). Поскольку у нас есть оба варианта, нам нужно добавить счетчики: N[i][j] = N[i+1][j] + N[i+1][j+1].

Чтобы найти N[0][0] с помощью динамического программирования, нам нужно заполнить таблицу N. Сначала нам нужно установить границу таблицы:

N[m][j] = 0, for 0 <= j < n
N[i][n] = 1, for 0 <= i <= m

Из-за зависимостей в рекурсивном отношении мы можем заполнить оставшуюся часть цикла цикла i назад и j вперед:

for (int i = m-1; i >= 0; i--) {
    for (int j = 0; j < n; j++) {
        if (S[i] == T[j]) {
            N[i][j] = N[i+1][j] + N[i+1][j+1];
        } else {
            N[i][j] = N[i+1][j];
        }
    }
}

Теперь мы можем использовать наиболее важный трюк алгоритма: мы можем использовать 1-мерный массив f с инвариантом во внешнем цикле: f = N[i+1]; Это возможно из-за того, как заполняется таблица. Если мы применим это к моему алгоритму, это даст:

f[j] = 0, for 0 <= j < n
f[n] = 1

for (int i = m-1; i >= 0; i--) {
    for (int j = 0; j < n; j++) {
        if (S[i] == T[j]) {
            f[j] = f[j] + f[j+1];
        } else {
            f[j] = f[j];
        }
    }
}

Мы почти по алгоритму вы дали. Прежде всего, нам не нужно инициализировать f[j] = 0. Во-вторых, нам не нужны назначения типа f[j] = f[j].

Так как это код C++, мы можем переписать фрагмент

if (S[i] == T[j]) {
    f[j] += f[j+1];
}

f[j] += (S[i] == T[j]) * f[j+1];

и все. Это дает алгоритм:

f[n] = 1

for (int i = m-1; i >= 0; i--) {
    for (int j = 0; j < n; j++) {
        f[j] += (S[i] == T[j]) * f[j+1];
    }
}

Ответ 2

Я думаю, что ответ замечательный, но что-то может быть неправильным.

Я думаю, что мы должны перебирать назад по i и j. Затем мы переходим к массиву N в массив f, мы зацикливаем j вперед, чтобы не перекрывать результат, полученный последним.

for (int i = m-1; i >= 0; i--) {
    for (int j = 0; j < n; j++) {
        if (S[i] == T[j]) {
            N[i][j] = N[i+1][j] + N[i+1][j+1];
        } else {
            N[i][j] = N[i+1][j];
        }
    }
}

Ответ 3

Ну, проблема динамического программирования. Пусть сначала определим его состояние dp [i] [j] как число различных подпоследовательностей t [0..i - 1] в s [0..j - 1]. Тогда у нас есть следующие уравнения состояния:

General case 1: dp[i][j] = dp[i][j - 1] if t[i - 1] != s[j - 1];
General case 2: dp[i][j] = dp[i][j - 1] + dp[i - 1][j - 1] if t[i - 1] == s[j - 1];
Boundary case 1: dp[0][j] = 1 for all j;
Boundary case 2: dp[i][0] = 0 for all positive i.

Теперь давайте кратко объясним четыре уравнения выше.

If t[i - 1] != s[j - 1], the distinct subsequences will not include s[j - 1] and thus all the number of distinct subsequences will simply be those in s[0..j - 2], which corresponds to dp[i][j - 1];
If t[i - 1] == s[j - 1], the number of distinct subsequences include two parts: those with s[j - 1] and those without;
An empty string will have exactly one subsequence in any string :-)
Non-empty string will have no subsequences in an empty string.

Собрав их вместе, мы получим следующие простые коды (как перевод :-)):

class Solution {
public:
    int numDistinct(string s, string t) {
        int m = t.length(), n = s.length();
        vector<vector<int>> dp(m + 1, vector<int> (n + 1, 0));
        for (int j = 0; j <= n; j++) dp[0][j] = 1;
        for (int j = 1; j <= n; j++)
            for (int i = 1; i <= m; i++)
                dp[i][j] = dp[i][j - 1] + (t[i - 1] == s[j - 1] ? dp[i - 1][j - 1] : 0);
        return dp[m][n];
    }
};

Обратите внимание, что мы сохраняем всю матрицу m * n просто для dp [i - 1] [j - 1]. Таким образом, мы можем просто сохранить это значение в одной переменной и дополнительно оптимизировать сложность пространства. Окончательный код выглядит следующим образом.

class Solution {
public:
    int numDistinct(string s, string t) {
        int m = t.length(), n = s.length();
        vector<int> cur(m + 1, 0);
        cur[0] = 1;
        for (int j = 1; j <= n; j++) { 
            int pre = 1;
            for (int i = 1; i <= m; i++) {
                int temp = cur[i];
                cur[i] = cur[i] + (t[i - 1] == s[j - 1] ? pre : 0);
                pre = temp;
            }
        }
        return cur[m];
    }
};