Como melhorar a solução de problemas de programação dinâmica

Recentemente, deparei-me com esta pergunta: "Você recebe uma expressão booleana que consiste em uma sequência de símbolos 'verdadeiro', 'falso', 'e', ​​'ou' e 'xor'. Conte o número de maneiras entre parênteses expressão que será avaliada como verdadeira. Por exemplo, existem duas maneiras de colocar parênteses 'verdadeiro e falso xor verdadeiro', de modo que seja avaliado como verdadeiro ".

Eu sabia que era um problema de programação dinâmica, então tentei criar uma solução sozinha, que é a seguinte. Suponha que tenhamos uma expressão como ABC .... D onde '.' representa qualquer uma das operações e, ou, xor e as letras maiúsculas representam verdadeiro ou falso. Digamos que o número de maneiras para essa expressão do tamanho K produzir uma verdade é N. Quando um novo valor booleano E é adicionado a essa expressão, existem duas maneiras de colocar parênteses essa nova expressão 1. ((ABC .... D) .E) ie. com todos os parênteses possíveis de ABC .... D, adicionamos E no final. 2. (ABC (DE)) ie. avalie DE primeiro e depois encontre o número de maneiras pelas quais essa expressão do tamanho K pode produzir true.

suponha que T [K] é o número de maneiras pelas quais a expressão com tamanho K produz true, então T [k] = val1 + val2 + val3 em que val1, val2, val3 são calculados da seguinte maneira.

1) quando E é agrupado com D.

i) Não altera o valor de D

ii) inverte o valor de D

no primeiro caso, val1 = T [K] = N. (Como isso se reduz à expressão inicial ABC ... D). No segundo caso, reavaliar dp [K] com o valor de D revertido e esse é val1.

2) quando E é agrupado com toda a expressão.

// val2 contém o número de 'true' que E produzirá com expressões que deram 'true' entre todas as instâncias entre parênteses de ABC ...... D i) se true.E = true então val2 = N

ii) se verdadeiro.E = falso, então val2 = 0

// val3 contém o número de 'true' que E produzirá com expressões que deram 'false' entre todas as instâncias entre parênteses de ABC ...... D

iii) se falso.E = verdadeiro, então val3 = (2 ^ (K-2) - N) = M ie. número de maneiras pelas quais a expressão com tamanho K produz um falso [2 ^ (K-2) é o número de maneiras entre parênteses com uma expressão do tamanho K].

iv) se false.E = false então val3 = 0

Essa é a idéia básica que eu tinha em mente, mas quando verifiquei a solução http://people.csail.mit.edu/bdean/6.046/dp/dp_9.swf, a abordagem foi completamente diferente. Alguém pode me dizer o que estou fazendo de errado e como posso melhorar a resolução de DP para que eu possa encontrar soluções como a que foi fornecida acima.

Desde já, obrigado.

A resposta, como em muitas coisas, é:

Prática, prática, prática.

A propósito, acredito que na sua solução você chegou a um beco sem saída cometendo um erro trivial desde o início: "Existem duas maneiras de colocar parênteses nessa nova expressão" - não existem mais de duas? Que tal (A.B.(C.D.E)), por exemplo?

Concordo com o occulus que a prática é mais necessária, e também gostaria de acrescentar que você precisa prestar atenção no reconhecimento dos padrões nos problemas que podem ser resolvidos usando o DP (isso é explicado muito bem no CLRS)

Você pode encontrar problemas de spoj que envolvem programação dinâmica aqui :)