Solução Problema da semana 40 intermediário

Conhecimentos Prévios

- Programação Dinâmica

Problemas como esse, que envolvem  determinar se uma certa cadeia de parênteses, chaves ou colchetes é válida ou não, são clássicos. E inclusive já caíram na obi! Mas não se preocupe. vou explicar essa ideia aqui.

Como checar se uma cadeia é válida

Primeiro, vou mostrar como resolver para o caso onde só há parênteses, considerando que os pontos de interrogação foram determinados como uma das duas opções. Depois, vou mostrar como fazer quando há outras possibilidades. Mesmo que não seja necessária nesse problema, essa técnica é importante o suficiente para ser mencionada. Se você só quiser saber a solução desse problema, basta pular as partes com outras possibilidades.

Caso só com parênteses

Para determinar se uma cadeia é válida ou não, vamos fazer o seguinte: mantemos uma variável auxiliar $aux$, inicialmente $0$, e passamos pela sequência e quando encontramos '(', somamos 1 em aux e quando encontrarmos ')' subtraímos 1 de aux. Para verificar que ela é válida, basta ver se $aux$ não fica negativo em nenhum momento e se ela não acaba em um número diferente de 0. Se não, a sequência é válida. Pensar por quê isso basta fica de tarefa (｡•̀ᴗ-), mas é bem intuitivo.

Caso com mais possibilidades

Para o caso com mais possibilidades, podemos manter uma stack com os "caracteres de abertura", como '(' e '[', enquanto vamos passando pela sequência. Quando encontramos um "caracter de fechamento", como ')' e ']', checamos o elemento no topo da stack. Se a stack não estiver vazia e o elemento no topo complementar o caracter de fechamento, por exemplo, '(' está no topo e ')' é o caracter de fechamento que estamos processando, podemos retirar o elemento no topo da stack e seguir para o próximo elemento na sequência. Se não encontrarmos nenhum problema, isto é, se não processarmos nenhum caracter de fechamento com a stack vazia, e não vermos que o caracter no topo da stack não é compatível com o caracter sendo processado e não acabarmos de processar a sequência com a stack não vazia, a sequência é válida. Novamente, pense por que isso basta (｡•̀ᴗ-).

Solução Final

Agora que sabemos como checar se uma sequência é válida ou não, vamos para o problema em si. Vimos a técnica de checagem que utiliza um número para guardar o número de caracteres do tipo '(' que vieram antes. Nós vamos usar isso na nossa dp. Para isso, vamos chamar o número dessa técnica de $C$ e fazer uma $dp[i][j]$, que guarda, para o índice i na string, o número de maneiras de formar uma string de parênteses até o índice $i$, inclusive, com $C = j$. Isto é, o número de maneiras de formar a string até o índice $i$ se tivermos $j$ parênteses "abertos".

Vamos chamar a string com '(', ')' e '?' de $S$.

Para calcular a dp, vamos passar pelos índices da string de $0$ até $s.size() - 1$ e para cada índice testar o valor $C$ de $0$ até $s.size()$ e depois disso, basta analisar alguns casos:

• Se $S[i] = '('$
  • Se $j = 0$, não fazemos nada, $dp[i][j] = 0$.
  • Se $j > 0$, $dp[i][j] = dp[i - 1][j - 1]$, isso porque haverão tantas possibilidades quanto no índice anterior com $C = j - 1$ , já que $S[i] = '('$, $C$ é acrescido de $1$ e o número de possibilidades não muda.
• Se $S[i] = ')'$
  • $dp[i][j] = dp[i-1][j+1]$, porque são as mesmas possibilidades do índice anterior, e $C$ diminuí em $1$, já que "fechamos" uma parênteses que estava aberto.
• Se $S[i] = '?'$
  • Agora temos que aumentar o número de possibilidades, já que pode ser tanto '(' ou ')'.
  • Considerando o primeiro caso:
    • Se $j = 0$, não fazemos nada, $dp[i][j] = 0$.
    • Se $j > 0$, $dp[i][j] += dp[i - 1][j - 1]$.
  • Considerando o segundo caso:
    • $dp[i][j] += dp[i-1][j+1]$.
  • Note que estamos fazendo $+=$ ao invés de simplesmente setar o valor.
  • Lembre também de tirar o módulo após somar.

Segue o código para maior clareza: