Page 1 of 1
I NEED HELP WITH DYNAMIC PROGAMMING
Posted: Sun Sep 24, 2006 1:49 pm
by 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...
Re: I NEED HELP WITH DYNAMIC PROGAMMING
Posted: Sun Sep 24, 2006 11:22 pm
by Mg9H
Yaron Wittenstein wrote: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 ?
Posted: Mon Sep 25, 2006 8:30 am
by 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...