Можно ли преобразовать это рекурсивное решение в DP для задачи «Valid Parenthesis String»?

Question

Контекст: я пытаюсь изучить динамическое c программирование, придумывая рекурсивное решение и затем кэшируя результаты подзадач.

Я действительно боролся с этой проблемой LeetCode.

Учитывая строку, содержащую только три типа символов: '(', ')' и '*', напишите функцию для проверки правильности этой строки. Мы определяем действительность строки по следующим правилам:

Любая левая скобка '(' должна иметь соответствующую правую скобку ')'. Любая правая скобка ')' должна иметь соответствующую левую скобку '('. Левая скобка '(' должна go перед соответствующей правой скобкой ')'. '*' Может рассматриваться как одиночная правая скобка ')' или одиночная левая скобка '(' или пустая строка. Также допустима пустая строка.

Пример 1:

Input: "()", Output: True

Пример 2:

Input: "(*)", Output: True

Пример 3:

Input: "(*))", Output: True

Мне удалось найти рекурсивное решение, которое, кажется, работает. Однако я не в состоянии преобразовать его в DP, я даже не понимаю, с чего мне начать или что я должен кэшировать, т.е. я не вижу, как результаты поддеревьев рекурсии одинаковы для разных подзадач. существующее решение DP . Но я не могу связать его с рекурсивным. Возможно ли даже преобразовать это конкретное решение в DP? Я был бы очень признателен за предложения.

Вот мой код:

class Solution {
public:
    bool checkValidString(string s) {
        stack<int> paren_stack;
        int ind = 0;
        return check_valid_rec(s, ind, paren_stack);
    }

private:
    bool check_valid_rec(string& s, int ind, stack<int> paren_stack) {

        if (ind >= s.size())
            return paren_stack.empty();

        while (s[ind] != '*' && ind < s.size()) {
            if (s[ind] == '(')
                paren_stack.push('(');
            else {
                if (!paren_stack.empty() && paren_stack.top() == '(')
                    paren_stack.pop();
                else return false;
            }
            ind++;
        }

        if (ind >= s.size())
            return paren_stack.empty();

        // if '*', there are three options
        // 1. ignore '*'
        bool ignore = check_valid_rec(s, ind + 1, paren_stack);
        // 2. replace with '('
        s[ind] = '(';
        bool left_replace = check_valid_rec(s, ind, paren_stack);
        // 3. replace with ')'
        s[ind] = ')';
        bool right_replace = check_valid_rec(s, ind, paren_stack);

        if (ignore || left_replace || right_replace)
            return true;
        else 
            return false;
    }
};

Answer 1

Ваше решение является примером возврата. Он не подчиняется перекрывающемуся свойству . Ссылка на решение dp, которой вы поделились, содержит правильный подход. Это также легко реализовать как recusrion, а также дп.

Если вы все еще хотите придерживаться своего подхода (или чего-то подобного), вы должны настроить свой путь, чтобы подчиняться свойству перекрывающихся подзадач. Я имею в виду подход, который вы, возможно, можете рассмотреть:

1. Start from the end of the given string.
2. Instead of a stack, maintain the count of left and right paranthesis.
3. Psudocode for recursion:
bool foo(pos,count_left_paranthesis,count_right_paranthesis):
    if count_left_paranthesis >  :
        return false;
    if (pos < 0)
        return count_left_paranthesis == count_right_paranthesis;
    if string[pos] == '(':
        return foo(pos-1,count_left_paranthesis+1,count_right_paranthesis);
    else if string[pos] == '):
        return foo(pos-1,count_left_paranthesis,count_right_paranthesis+1);
    else: // string[pos] = '*'
        return foo(pos-1,count_left_paranthesis,count_right_paranthesis) 
                  || foo(pos-1,count_left_paranthesis,count_right_paranthesis+1) 
                  || foo(pos-1,count_left_paranthesis+1,count_right_paranthesis)
4. Memoize the results of the subproblems.

Хотя существуют более простые решения.

Я сам попробовал вышеизложенное, и вот рабочее решение. Удивительно, но это даже было принято.

class Solution {
public:
    map<vector<int>,bool> dp;
    bool foo(const string& s, int pos, int lc, int rc)
    {
        if (lc > rc) return false;
        if (pos<0)
        {
            return lc == rc;
        }
        vector<int> v = {pos,lc,rc};
        if (dp.find(v) != dp.end()) return dp[v];
        if (s[pos] == '(')
        {
            return dp[v] = foo(s,pos-1,lc+1,rc);
        }
        else if (s[pos] == ')')
        {
            return dp[v] = foo(s,pos-1,lc,rc+1);
        }
        else
        {
            return dp[v] = (foo(s,pos-1,lc,rc) || foo(s,pos-1,lc+1,rc) || foo(s,pos-1,lc,rc+1));
        }
    }
    bool checkValidString(string s) {
        return foo(s,s.size()-1,0,0);
    }
};

• Еще одна быстрая оптимизация может заключаться в использовании вектора для запоминания, но я ленивый.
• хорошо, вы даже можете начать с самого начала строки. Начать со спины было проще для меня.

Примечание: Это ни в коем случае не самый эффективный способ решения проблемы, это просто помочь оператору с рекурсивное решение, а затем придумать dp-решение со средствами запоминания (или « кэширование результатов подзадач »)

Answer 2

Сначала ваш стек содержит только '(', поэтому он может быть просто счетчиком.

s является "почти" постоянной величиной, поэтому у вас есть только ind, left_counter в качестве переменной для dp:

std::vector<std::vector<bool>> dp(s.size() + 1, std::vector<bool>(s.size(), false));

и dp[0][0] получили ваш окончательный результат.

Теперь инициализация:

if (ind >= s.size())
    return paren_stack.empty();

, поэтому dp[s.size()][0] = true;

Теперь, переходя от одного столбца к другому (в нашем случае в предыдущем случае :)) (пытаясь сохранить ваши логи c как можно больше):

switch (s[ind]) {
    case '*':
        dp[ind][j] = dp[ind + 1][j] /* Empty */
                   | (j > 0 && dp[ind + 1][j - 1]) /* ) */
                   | (j + 1 < s.size() && dp[ind + 1][j + 1]) /* ( */
                   ;
                   break;
    case '(': dp[ind][j] = (j + 1 < s.size() && dp[ind + 1][j + 1]); break;
    case ')': dp[ind][j] = (j > 0 && dp[ind + 1][j - 1]); break;
}

Окончательный результат:

bool is_balanced(const std::string& s)
{
    if (s.empty()) return true;

    std::vector<std::vector<bool>> dp(s.size() + 1, std::vector<bool>(s.size(), false));

    dp[s.size()][0] = true;

    for (int ind = s.size() - 1; ind >= 0; --ind) {
        for (std::size_t j = 0; j != s.size(); ++j) {
            switch (s[ind]) {
                case '*':
                    dp[ind][j] = dp[ind + 1][j] /* Empty */
                               | (j > 0 && dp[ind + 1][j - 1]) /* ) */
                               | (j + 1 < s.size() && dp[ind + 1][j + 1]) /* ( */
                               ;
                               break;
                case '(': dp[ind][j] = (j + 1 < s.size() && dp[ind + 1][j + 1]); break;
                case ')': dp[ind][j] = (j > 0 && dp[ind + 1][j - 1]); break;
            }
        }
    }
    return dp[0][0];
}

Демо