Cara menjadi lebih baik dalam memecahkan masalah pemrograman Dinamis

Saya baru-baru ini menemukan pertanyaan ini: "Anda diberi ekspresi boolean yang terdiri dari serangkaian simbol 'benar', 'salah', 'dan', 'atau', dan 'xor'. Hitung jumlah cara untuk mempasangkan ekspresi sedemikian rupa sehingga akan dievaluasi menjadi benar. Misalnya, ada dua cara untuk mempatenkan 'benar dan salah atau benar' sedemikian sehingga ia mengevaluasi ke benar. "

Saya tahu ini adalah masalah pemrograman yang dinamis jadi saya mencoba untuk mencari solusi sendiri yaitu sebagai berikut. Misalkan kita memiliki ekspresi sebagai ABC .... D mana '.' mewakili salah satu operasi dan, atau, xor dan huruf kapital mewakili benar atau salah. Katakanlah jumlah cara untuk ekspresi ukuran K ini untuk menghasilkan true adalah N. ketika nilai boolean baru E ditambahkan ke ekspresi ini, ada 2 cara untuk menyisipkan ekspresi baru ini 1. ((ABC .... D) .E) yaitu. dengan semua kemungkinan tanda kurung ABC .... D kita tambahkan E di akhir. 2. (ABC (DE)) yaitu. evaluasi DE terlebih dahulu dan kemudian temukan jumlah cara yang bisa dihasilkan oleh ekspresi ukuran K ini.

misalkan T [K] adalah jumlah cara ekspresi dengan ukuran K menghasilkan true maka T [k] = val1 + val2 + val3 di mana val1, val2, val3 dihitung sebagai berikut.

1) ketika E dikelompokkan dengan D.

i) Itu tidak mengubah nilai D

ii) itu berbanding terbalik dengan nilai D

dalam kasus pertama val1 = T [K] = N. (Karena ini mengurangi ke ekspresi ABC ... D awal). Dalam kasus kedua mengevaluasi kembali dp [K] dengan nilai D terbalik dan itu adalah val1.

2) ketika E dikelompokkan dengan seluruh ekspresi.

// val2 berisi jumlah 'benar' yang akan dihasilkan oleh E dengan ekspresi yang memberi 'benar' di antara semua instance ABC ...... D i) jika true.E = true lalu val2 = N

ii) jika true.E = false maka val2 = 0

// val3 berisi jumlah 'benar' yang akan dihasilkan oleh E dengan ekspresi yang memberi 'salah' di antara semua contoh yang ditulis dalam kurung ABC ...... D

iii) jika false.E = true maka val3 = (2 ^ (K-2) - N) = M yaitu. sejumlah cara ekspresi dengan ukuran K menghasilkan false [2 ^ (K-2) adalah sejumlah cara untuk mempasteheskan ekspresi ukuran K].

iv) jika false.E = false maka val3 = 0

Ini adalah ide dasar yang ada dalam pikiran saya tetapi ketika saya memeriksa solusinya http://people.csail.mit.edu/bdean/6.046/dp/dp_9.swf pendekatan di sana sama sekali berbeda. Dapatkah seseorang memberi tahu saya apa yang saya lakukan salah dan bagaimana saya bisa lebih baik dalam menyelesaikan DP sehingga saya dapat menemukan solusi seperti yang diberikan di atas sendiri.

Terima kasih sebelumnya.

Jawabannya, seperti banyak hal, adalah:

Berlatih, berlatih, berlatih.

Ngomong-ngomong, saya percaya bahwa dalam solusi Anda, Anda menemui jalan buntu dengan membuat kesalahan sepele sejak dini: "Ada 2 cara untuk membatasi ekspresi baru ini" - bukankah ada lebih dari 2? Bagaimana dengan (A.B.(C.D.E)), misalnya?

Saya setuju dengan occulus bahwa latihan adalah yang paling dibutuhkan, juga ingin menambahkan bahwa Anda perlu memperhatikan dalam mengenali pola masalah yang dapat diselesaikan dengan menggunakan DP (ini dijelaskan dengan cukup baik di CLRS)

Anda dapat menemukan masalah spoj yang melibatkan pemrograman dinamis di sini :)