I NEED HELP WITH DYNAMIC PROGAMMING

[Yaron Wittenstein]

Hi
This link has 3 questions of dynamic programming
I dont know how to solve the first question (Interleaving)
http://www.cs.berkeley.edu/~jordan/cou ... s/hw9.pdf

If someone knows please help me!
what should be the recurrence, base conditions and why?

Thanx...

[Mg9H]

Hi
This link has 3 questions of dynamic programming
I dont know how to solve the first question (Interleaving)
http://www.cs.berkeley.edu/~jordan/cou ... s/hw9.pdf

If someone knows please help me!
what should be the recurrence, base conditions and why?

Thanx...

DP array D [N][L1][L2] where N = |S|, L1 = |x| and L2 = |y|

D [a] = true if the S_i (the string consists of the first i characters of S) can be partition into 2 subsequences X and Y, s.t. X = (x^k)x[1]x[2]..x[a] and Y = (y^k')y[1]y[2]...y

Otherwise D [a] = false

Finally, s is an interleaving of x and y iff there exists some a, b such that D [|s|][a] = true

btw, are you from UCBerkeley ?

[Yaron Wittenstein]

Thank you!
I'm not from UCBerkeley (just studying DP)

I'm not sure what do you mean by writing: X = (x^k)x[1]x[2]..x[a]

My problem it how to use the sub-problems I mean
how D[a] depends on D[a'][b'] ?
if you can please write the recurrence
thanx...