On Jul 23, 2016 9:27 AM, "monik...@netzero.net" <monik...@netzero.net> wrote: > > IM sorry I do not understand: > > For array A of length N, and for an integer k < N: > -- By k do you mean value of k or position of k in the list? >
The letter 'k' is typically intended to be used as an index, a position into a list. I'm trying to say that k had to be pointed somewhere in the list by constraining it to be less than the size of the list. > > 1. If we know L(A, 1), L(A, 2), ... all the way to L(A, N), then > we can just look at the maximum value of those pieces. That's going > to be a solution to the general problem. > -- By maximum value do you mean I have to sum up the values in the list? Why? "Maximum" is a notion of comparing and picking out the biggest thing we see. It doesn't have to do with addition. If we have a bunch of numbers, we can do a lot more than just add then together. Numbers are more interesting than that. Both summation and maximum-finding are operations that are intended to take a bunch of bits of information in order to discover something new. So, conceptually speaking, there *is* a deep, underlying connection. But I don't think that's what you're intending to talk about. > 2. For a subproblem L(A, k), if we know the values for L(A, 1), > L(A, 2), ... , L(A, k-1), then we can compute L(A, k) by looking at > those other subproblems: the result of L(A, k) is related to them. > -- How do we find those subproblems? And then how do you relate them to the main problem? > > Can you please explain more in details? Unfortunately, no. This is the wrong venue. Please: I strongly encourage you to talk with your professor or study group: it really does sound like this is the first time you've seen these kinds of concepts. Longest common subsequence is not the ideal problem to use to introduce these concepts: it is meant to help you *master* them. I would not dare trying to use it as a first example into learning dynamic programming. You probably want to use a problem that has fewer moving parts. Your instructor likely has a much nicer introductory problem so that you can learn the patterns of thinking through these problems. Anyway, hope that makes sense. _______________________________________________ Tutor maillist - Tutor@python.org To unsubscribe or change subscription options: https://mail.python.org/mailman/listinfo/tutor
