Please help me to understand dynamic programming

[D.J. Quavern]

I am not sure I should post in Paradigms, and even less if my problem is a Logic programming problem, but some logic is definitely involved.

I am going through the Grokking Algorithm chapter 9 (https://www.manning.com/books/grokking-algorithms) and I cannot fill the example that is given.

The author explains that the point with dynamic programming is to optimize every row by filling the maximum value given the constraints. In this example, we are trying to steal for a max value between a guitar (1lb, 1500$), a stereo (4lb, 3000$) and a laptom (3lb, 2000$). I can follow the example and I understand that at each stage, we choose between the previous max located at table[row-1][column] and the current object + the top value of what we can stuff for the place that is left. And as I understand, we do not need to calculate the top value for the place that is left, since this value is in the table.

Anyways, that's the process that you very likely are all familiar with.
https://imgur.com/a/CuAY5wK

When it comes to do it yourself, I just cannot get 2 cells.
What's going on in the green cell? I thought we were supposed to choose according to the formula, that is to say, previous max value OR current object + optimum value for the place that is left. In that case, the place which is left is one half day, and the optimum is westminster, NOT the globe!
The red cell: I know that the reply is Westminster, National Gallery and St Paul for a rating of 24... but I don't understand how we get it with the formula.

[Piet Souris]

hi DJ,

excuses for the long wait! Shame on us...

As you write, each element (i, j) in the grid is the maximum of element(i-1, j) (the element right above) and the element right above shifted w(i) places to the left + the value of element i.
In other words: the final red cell is the maximum of the element above(22) and the element above left (16) + 8 = 24.

It is an ingenious system and works beautifully!

You now have the days (weights) in periods of half days, it might be a little more clear when you turn that into integers. Thus .5, .5, 1, 2, .5 with a "total capacity (Knapsack term)"of 2, making 1, 1, 2, 4, 1 with a capacity of 4. Then it is clear that for the red cell you take the max of the cell above, and the cell above, shifted one place to the left (since the weight is 1).

With the given data: values  7, 6, 9, 9, 8
                              weights 1, 1, 2, 4, 1

You wold then get the scheme:
             j =
i   element   0   1    2    3   4
0     -       0   0    0    0   0
1     7       0   7    7    7   7
2     6       0   7   13   13  13
3     9       0   7   13   16  22
4     9       0   7   13   16  22
5     8       0   8   15   21  24

So for the last line it holds:

8 = max(7, 0 + 8)
15 = max(13, 7 + 8)
21 = max(16, 13 + 8)
24 = max(22, 16 + 8)

and the right bottom element is the max alltogether.


Edit: I forgot to talk about the green cell. Well, the weight (nr of days) of the National Gallery is 1, but since your unit is a half day, tyou should look two columns to the left (that's why I advised to use integers for the weights). So the green cell is max(13 (cell above), 13 + 9) (the second 13 being the value of (globe, day 1).

[D.J. Quavern]

Piet Souris wrote:hi DJ,

excuses for the long wait! Shame on us...

No worries!
I know you like and work in Java, I am just grateful that you take the time to reply to my random questions .

Piet Souris wrote:

You now have the days (weights) in periods of half days, it might be a little more clear when you turn that into integers. Thus .5, .5, 1, 2, .5 with a "total capacity (Knapsack term)"of 2, making 1, 1, 2, 4, 1 with a capacity of 4. Then it is clear that for the red cell you take the max of the cell above, and the cell above, shifted one place to the left (since the weight is 1).


You wold then get the scheme:
             j =
i   element   0   1    2    3   4
0     -       0   0    0    0   0
1     7       0   7    7    7   7
2     6       0   7   13   13  13
3     9       0   7   13   16  22
4     9       0   7   13   16  22
5     8       0   8   15   21  24

So for the last line it holds:

8 = max(7, 0 + 8)
15 = max(13, 7 + 8)
21 = max(16, 13 + 8)
24 = max(22, 16 + 8)

and the right bottom element is the max alltogether.


Edit: I forgot to talk about the green cell. Well, the weight (nr of days) of the National Gallery is 1, but since your unit is a half day, tyou should look two columns to the left (that's why I advised to use integers for the weights). So the green cell is max(13 (cell above), 13 + 9) (the second 13 being the value of (globe, day 1).

Yes! I kind of got it later and I am glad you confirm. I was confused by the 1/2 a day unit. But yes, it makes sense now. If you look at the second row (visiting the globe), it's either Westminster or the value of 1 - 0.5 (let's imagine they are integers now )), which is 7 + the globe value (6).

Thank you Piet! Can one nominate you for a cow, for kindness and beautiful matrix?


I of course have a follow up question. How does it work for the shortest sub sequence (the book keeps on with more dynamic programming)?

[Piet Souris]

hi DJ,

the pleasure is all mine, or whoever of this commumnity is helping you.

And to the cow suppliers: whoever you are, thanks!

But now for your latest question. What exactly is the problem? There are some variants, like longest common subsequence of two Strings, shortest subsequnce in String S that is not in String T, and the variants that use substrings instead of subsequences. I followed that Grokking book that you linked to in your opening post, and I came as far as the longest common subsequence. But they make the text unreadable, so I have to follow the diagrams (I like the book, on the look of it, though!). Should I have read further?

[D.J. Quavern]

Piet Souris wrote:hi DJ,

the pleasure is all mine, or whoever of this commumnity is helping you.

And to the cow suppliers: whoever you are, thanks!

But now for your latest question. What exactly is the problem? There are some variants, like longest common subsequence of two Strings, shortest subsequnce in String S that is not in String T, and the variants that use substrings instead of subsequences. I followed that Grokking book that you linked to in your opening post, and I came as far as the longest common subsequence. But they make the text unreadable, so I have to follow the diagrams (I like the book, on the look of it, though!). Should I have read further?

I think the book was great, but more for beginners like me.
Here is the part on the longuest subsequence:
https://imgur.com/a/gaCNwoa

I was wondering if you could use it to calculate shortest substring? I was thinking of a programming problem where you needed to find the shortest sequence of letters to insert in an alphabetical sequence, to complete all the letters that are missing with the minimal amount of letters.
This is poorly explained of me, so I should just link the problem !

[Piet Souris]

hi DJ,

shortest substring? Yes, you can do that using DP, but why should you? If S and T are both Strings, then either they have a character in common (so the shortest substring is that letter) or they have no character in common, and then there is no common substring at all. Can you do such a check?

And similar, the problem at Kattis is slightly more complicated, but not much, and you do not need DP for it. For instance, if I have the String A = "abcdefghijklmnopqrstuvwxyz", and I have another String B = "djquavern", and suppose I remove from A all the characters that appear in B. Then A still has one or more characters. What does that mean for wanting to make B an alphabetical String?

Edit: oops, I just gave that exercise another read, and I overlooked that an alphabetical String must have the letters 'a' - 'z' in order. Hang on a bit, I need a slight rethinking...

[Piet Souris]

Well, I have come this far:

if the given String does NOT contain an 'a', then what do we need to add to make that String an alphabetical String?
if the String does contain an 'a', but there is no 'b' following that 'a', then what?
Now, 'a' and 'b' are present, in that order, but counting from 'b', there is no 'c'. Then what?
et cetera.

I was unable to come up with a decent DP solution. The problem being that if the String is "agb", then the 'g' plays no role in the solution. The question would be "what is the shortest subsequence, given String "agb", into the String "abcdefghijklmnopqrstuvwxyz". But maybe I'm just asking the wrong question

However, the solution is not that difficult. It boils down to, for instance, having the String "dbbbaghkbhhhhz" being transformd to "ab" and to conclude from this that we need to add 24 characters. I used as helper method this routine:

private static int findNextIndex(char[] arr, char toFind, int fromIndex) {
    for (int index = fromIndex; index < arr.length; index++) {
        if (arr[index] == toFind) return index;
    }
    return -1;
}

It is an O(N) procedure, so should be fast enough.

[D.J. Quavern]

I will ponder a bit and come back!

Edit: I'm back!

You wrote :

Piet Souris wrote:
The problem being that if the String is "agb", then the 'g' plays no role in the solution.

And sure enough, it works for short strings! We say the the alphabet was 6 letters, a to f. If we have the string adbef, we can go from a -> b (with d playing no role in the solution), then add c and d. So we added 2 letters to make it alphabetical. It was quite an eye opener and I think we are definitely on something   ! I'm very excited  
We can also go a -> d (adding b and c), with the b after the d not playing any part of in the solution.

But what about longer strings? For the sequence "aiemckgobjfndlhp", if we go from a-> b, than from b -> d (adding one letter, since there is no c), then from d-> h (adding 3 letters, there are no e, f, g), and then from h -> p (adding 7 letters to o). After p, we are missing 10 letters. So we come up with a grand total of 21 letters, which is not the most optimal solution. So I believe we need a system to choose the best letter, if the direct follower is not in the list?

[Piet Souris]

hi DJ,

you know what? This exercise makes me feel very old... when I read your reply, I thought you had misunderstood the exercise, so I just gave it another read. And I saw that I again had misread the exercise. I thought the missing characters had to be added at the end of the string, but now I see that they can be inserted at any place. Sigh, that makes all the difference, and now I understand your reply. So much for my selfconfidence....

But assuming I have finally understood the question, I see why your first post about this exercise was mentioning DP, and I must compliment you for coming up with this. Very clever!  And indeed, to me it boils down to the queston of what is the longest common  subsequence between the input string S and the alphabet "abc...z". I just had a look at GeeksForGeeks and they come up with a very short routine that uses DP. I just tested it, and it seems both oke (the longest common substring of your long string and the alphabet has length 6) and fast enough to handle strings of length 50.

Pffff........      

[D.J. Quavern]

Dear Piet,
I am sorry for the time I take to come back to you right now. I am a bit overwhelmed with work I need to do (.
I assure you that I really appreciate your replies and I always read them with great attention.
So yes, I ll be back shortly with another try, hopefully without checking geekforgeeks first!

[Piet Souris]

hi DJ,

well, as I said before: it is a pleasure doing business with you!    (but I mean it)

Take all the time you need, and don't forget there are much more important things in life than these nasty exercises (but then again not thàt many).

We'll all be here waiting for your next reply, however long that may take!

[D.J. Quavern]

Crap, I thought I got it! But I always get that the cheapest way is 21.

a to b = 0, b to d = 1, d to h = 3, h to p = 7, and p to z = 21.

Could it be a Dijkstra solution we are after, with the cheapest path?

Did you come up with a DP solution that worked for you? If so, could you link me the Geek for geeks routine you read about (I found way too much dynamic programming articles....)

It's my third edit ... Can you come up with a shorter mixed-up alphabet for which you know the right answer, so that I can test a shortest route algorithm with less letters ? I can't, as I don't know how those things work!

[Campbell Ritchie]

Why are you forbidding letters to map back to themselves? That was a feature of the Enigma Machine which made it vulnerable to deciphering.

[D.J. Quavern]

Campbell Ritchie wrote:Why are you forbidding letters to map back to themselves? That was a feature of the Enigma Machine which made it vulnerable to deciphering.

Hi Campbell!

Because this problem has to be alphabetical. 1. You can't go back. 2. If you have, let's say m, you don't need 2 m's, so m should not map to itself. You need to look, from m, if the letter that are right after are in alphabetical order.

PS: I am not planning to attack Germany any time soon anyway.

[Piet Souris]

I did not use Dijkstra, because I could not find any connection between this exercise and finding a shortest path.

I was considering this example:

String alphabet = "abcdef";
String input = "afcdeb";

We have the subsequences "ab", "af", "cde" et cetera, that are all subsequences in the alphabet as well. But the longest we can find is "acde". That has a length of 4, so we need to add 2 more letters. And indeed, we can obtain "aBfcdeFb" and that makes the input string alphabetic.

So, we go for the longest common subsequence between the inputstring and the alphabet. Now, I had no algorithm present, so I searched Google and found, among many more, this GeeksForGeeks site, that has many routines available:
https://www.geeksforgeeks.org/longest-common-subsequence-dp-4/
They also show how to use a grid if you want to solve it manually.

As an example, you can try, say:
alphabet = "abcdef"
input = "acdefbcdef"
Should give 0 characters to add.

[Campbell Ritchie]

D.J. Quavern wrote:. . . I am not planning to attack Germany any time soon anyway.

Hahahahahahahahahahahahaha!

[D.J. Quavern]

@Piet: I thought that the longest common subsequence required that the letters would be positioned next to each other? (like c would need to be in position 3, f in position 6, regardless of the letters you have between them?)
I will read the article you sent and will be back at some point in my life shortly! I promise!

@Campbell:  

[Piet Souris]

hi DJ,

no that is not required. A subsequence is just a subset of the characters, with the same order as the original String. So, if our input string is "djquavern" then dqn" is a subsequence, "avr"is one, et cetera. Just some characters, albeit that the order of the characters are the same as where they appear in the input string. So, "qja" is not a subsequence. If you require for a subsequence that the letters must be contiguous, then we are talking about substrings. Thus "dqn" is a subsequence but it is not a substring.

And by requiring that a subsequence is also a subsequence of our alphabet, we make sure that that subsequence is neatlly ordered (i.e. "dqn" is out of the question since the n appears after the q).

Meanwhile, waiting for that point in your life...    

[D.J. Quavern]

Piet Souris wrote:hi DJ,

no that is not required. A subsequence is just a subset of the characters, with the same order as the original String. So, if our input string is "djquavern" then dqn" is a subsequence, "avr"is one, et cetera. Just some characters, albeit that the order of the characters are the same as where they appear in the input string. So, "qja" is not a subsequence. If you require for a subsequence that the letters must be contiguous, then we are talking about substrings. Thus "dqn" is a subsequence but it is not a substring.

And by requiring that a subsequence is also a subsequence of our alphabet, we make sure that that subsequence is neatlly ordered (i.e. "dqn" is out of the question since the n appears after the q).

Meanwhile, waiting for that point in your life...    

I feel there is light in the tunnel -at least there is something to implement... - but I also feel stupid, that it takes me so long time to figure it out!

[Piet Souris]

Don't feel stupid, for this is a hard exercise, and I bet that not many were able to solve this.

I remember a Hackerrank exercise, where an array was given, with the question how many shifts were needed to get that array sorted. The arrays given were so large that brute force would take forever. Now, coming up with a clever idea was not difficult, but I needed a datastructure that I had never seen before. So, after days of very hard thinking, I came up with a beautiful structure that solved a 100.000 array in 2.5 seconds. So, with full pride I submitted my solution, only to find that five arrays gave a timeout error...

[D.J. Quavern]

Piet Souris wrote:Don't feel stupid, for this is a hard exercise, and I bet that not many were able to solve this.

I remember a Hackerrank exercise, where an array was given, with the question how many shifts were needed to get that array sorted. The arrays given were so large that brute force would take forever. Now, coming up with a clever idea was not difficult, but I needed a datastructure that I had never seen before. So, after days of very hard thinking, I came up with a beautiful structure that solved a 100.000 array in 2.5 seconds. So, with full pride I submitted my solution, only to find that five arrays gave a timeout error...

Hahaha, what an unexpected conclusion )! Thank you for sharing <3!

[D.J. Quavern]

Piet... we are almost there! THIS works... almost.


It crashes if I have repeted sequences, for example:

  a   b   a   b
a 1   1   2   2
b 1   2   2   3 nope! should still be 2!
c
d

[Piet Souris]

hi DJ,

please don't hold it against me, but there is something awkward I have to say. Here goes: your diagram has a tiny mistake!

First of all: when talking about row and col, these variables denote the length of the substrings we consider, and not, say, the characters at position string[row] or string[col]. If we talk about the element table[row][col], then we are talking about the longest common subsequence when considering the first 'row' characters of the first string, and the first 'col' characters of the second string. So, that is why that GeeksForGeeks routine started with:

for row in range(0, string1.length):
   for col in range(0, string2.length):
        if (row == 0 || col == 0) table[row][col] = 0

since in that case we are considering a substring of length 0, and we know for sure that the lcs has no elements.'

In your code, you do consider row and col as the indices into the two strings.

The rest of the code is:

if (string1[row - 1] == string2[col - 1]) then table[row][col] = 1 + table[row - 1][col - 1].
else table[row][col] = max(table[row - 1][col]. table[row, col - 1]).

Now, let's make your scheme again. But, like the table I showed in the beginning of this topic, I start with a colum and a row of just zeroes, representing the situations where row = 0 or col = 0:

row  char      col
               0     1     2    3    4
               -     a     b    a    b
0     -        0     0     0    0    0
1     a        0     1     1    1    1
2     b        0     1     2    2    2

Why do we get a value of 1 at position (1, 3)? Well, since the letters match, we apply the rule "1 + value left above", so we get 1 + 0 = 1.

Can you spot the mistake in your table?

[D.J. Quavern]

Piet Souris wrote:hi DJ,

please don't hold it against me, but there is something awkward I have to say. Here goes: your diagram has a tiny mistake!

First of all: when talking about row and col, these variables denote the length of the substrings we consider, and not, say, the characters at position string[row] or string[col]. If we talk about the element table[row][col], then we are talking about the longest common subsequence when considering the first 'row' characters of the first string, and the first 'col' characters of the second string. So, that is why that GeeksForGeeks routine started with:

for row in range(0, string1.length):
   for col in range(0, string2.length):
        if (row == 0 || col == 0) table[row][col] = 0

since in that case we are considering a substring of length 0, and we know for sure that the lcs has no elements.'

In your code, you do consider row and col as the indices into the two strings.

The rest of the code is:

if (string1[row - 1] == string2[col - 1]) then table[row][col] = 1 + table[row - 1][col - 1].
else table[row][col] = max(table[row - 1][col]. table[row, col - 1]).

Now, let's make your scheme again. But, like the table I showed in the beginning of this topic, I start with a colum and a row of just zeroes, representing the situations where row = 0 or col = 0:

row  char      col
               0     1     2    3    4
               -     a     b    a    b
0     -        0     0     0    0    0
1     a        0     1     1    1    1
2     b        0     1     2    2    2

Why do we get a value of 1 at position (1, 3)? Well, since the letters match, we apply the rule "1 + value left above", so we get 1 + 0 = 1.

Can you spot the mistake in your table?

I read the pseudo code in Grokking algorithms 😀
I don't have any paper unfortunately so I can't test it now, but do you mean that I should add some 0-padding to my table? This explains that...! I wondered if needing to wrap the indexes with Python was really the way to go!


If this is the mistake, it is not tiny. Way bigger than the tiny add at the bortom of the page!

[Piet Souris]

The zeroes that I added are not necessary, and I just read in the Grokking book that the author does not use them. It is just that I find these zeroes make the manual labour easier. If I am busy with the first row and I have to look to the left or up, or left and up, then there is a fysical row or column with zeroes, so that I do not need to think of these zeroes by hart. Well, it is a matter of personal taste. If you find them confusing, then just leave them out.

The GeeksForGeeks code has the extra line:

if (row == 0 or col == 0) then cell[row][col] = 0

That takes care of the zeroes in row 0 and in col 0. The rest of the code is identical to the grokking code.

When I was doing a course in Python (about 5 years ago) I quite liked that wrapping of array indices. You never get an IndexOutOfBounds-exception, but on the other hand, that may also be a bit dangerous, if that is not the intention and you forget to put a test into the code.

A question: the first excercise was about that dragon with many heads and even more tails. Sohail and I were advocating a DP solution, while you choose for a more direct approach (if I understood correctly). Now, if you had to do that exercise again, what would you do now?

[D.J. Quavern]

OMG!
Thank you so much. At last, it's solved!

Piet Souris wrote:The zeroes that I added are not necessary, and I just read in the Grokking book that the author does not use them. It is just that I find these zeroes make the manual labour easier. If I am busy with the first row and I have to look to the left or up, or left and up, then there is a fysical row or column with zeroes, so that I do not need to think of these zeroes by hart. Well, it is a matter of personal taste. If you find them confusing, then just leave them out.

The GeeksForGeeks code has the extra line:

if (row == 0 or col == 0) then cell[row][col] = 0

That takes care of the zeroes in row 0 and in col 0. The rest of the code is identical to the grokking code.

Piet Souris wrote:
What? How? How can he NOT use the zeros? How would you solve that without zeros?

Piet Souris wrote:
When I was doing a course in Python (about 5 years ago) I quite liked that wrapping of array indices. You never get an IndexOutOfBounds-exception, but on the other hand, that may also be a bit dangerous, if that is not the intention and you forget to put a test into the code.

A question: the first excercise was about that dragon with many heads and even more tails. Sohail and I were advocating a DP solution, while you choose for a more direct approach (if I understood correctly). Now, if you had to do that exercise again, what would you do now?

I honestly don't like it ! All my out of bounds error disappear but I have lots of unfathomable errors.


Well, for the hydra, I guess I need to make a table with several head and tail cutting opportunities and that my optimal result is zero?
Let me sleep on that!

[Piet Souris]

hi DP,

(if you don't mind me calling you that for the time being), well done! I had a look at the Grokking book, and I saw that this was the last part of the DP chapter. But before you start cheering: you know that story I told you about that Hackerrank exercise? Well, the structure I was so much looking for turned out to be invented in 1994, and it is called "Binary Indexed Tree", a brilliant structure. And you know what? I asked the author of the Grokking book recently if he also treated these things. He said "YES", so, something to look forward to?

But again: well done!


Edit: I almost missed your question:

DJ wrote:What? How? How can he NOT use the zeros? How would you solve that without zeros?

If you leave out the zero-row and zero-column, then you have to think of that zero yourself,' çause it's not physically there. Now, that is absolutely not difficult, it takes some practising, but it keeps your table neat. Well, as I said: personal taste.

I'm not fully consistent, by the wway. Remember the table at the beginning of this topic, about WestMinster and Globe et cetera? Well, one of the excursions took 1 day, and with a unit of a half day that means maybe looking TWO places to the left, so if I would have been consequent, I should have started the table with TWO zero columns. Ah well, noone's perfect, I guess...

[D.J. Quavern]

Sorry, my questions got all messed up in the quotes...!

I hear what you say ! Let's solve this exercice with a binary indexed weighted tree ! (in another threads!)

Yes, that's a thing to look forward to. I loved this book, it reads as easily as a bedtime story and with as much fun and useful life lessons.
I still don't get how to organise the DP table without the zeros, because it does not work for repeated sequences then?

[Piet Souris]

It has nothing to do with having these zeroes or not. Having them, like I do, just makes it a little more convenient for me. And it works for repeated sequences just as well. Here's an example of repeated sequences, without zeroes, and just keeping in mind these two rules:

1) if the characters match, then the value = 1 + value left above. If that value happens to be outside of the table, then take 0.
2) else take the maximum of the value left and the value above. Again, if either of these are outside the table, take 0 for such a value.

Let the strings be "abcd" and "abcdabcd". Then, without zeroes, we get this table
      a   b   c   d   a   b   c   d
a    1   1   1   1   1   1   1   1
b    1   2   2   2   2   2   2   2
c    1   2   3   3   3   3   3   3
d    1   2   3   4   4   4   4   4

Take the first row. We start with (a, a). These are equal, so we get the value = 1 + value left above. Now, that value is outside the table, so we take 0 and we get 1.
Stil on the first row, for the letters b, c, and d we get that we take the max of the values left and above. But since the values above are outside the table, we take 0, and so all the three values are 1. Next we get again (a, a). We apply the formula: 1 + value left above = 1 + outside the table = 1 + 0 = 1. Et cetera.
The fourth row: we start with (d, a), unequal, so we take the max of left and above, so 1. The same holds for (d,b) and (d, c): taking the max of the values left and above. Then we get (d,d). Equal, so we take 1 + value left above = 1 + 3 = 4. Et cetera. The last value is again (d, d) = 1 + 3 = 4. Done, without the zeroes and with repeats!

And don't worry: DP has nothing to do with BITs!

Here is a way to do the Heads and Tails with DP. For this, we put the number of heads horizontally and the number of tails vertically. And we translate the rules into some formulas (like we have done sofar in DP). If (h, t) denotes the number of moves to target when we have h heads and t tails, we get these formulas:

(h + 2, t)      = 1 + (h, t)
(h - 1, t + 2)  = 1 + (h, t)
(h, t - 1)      = 1 + (h, t)

provided the indices left are within the table (i.e. >= 0)

We start  with (0, 0) = 0. From this we get that (2, 0), (-1, 2) and (0, -1) have a value of 1, but the last two are invalid. Having set a 1 in (2, 0), we put a circle around the 0 of (0,0) so that we can see that we have processed (0, 0).
Next, from (2, 0) we get (4, 0) = 2 and (1, 2) = 2. We  encircle (2, 0) and go on processing (4, 0) and (2, 0). Et cetera!
We get this table:

  h    0   1   2   3   4   5   6 ...
t
0      0       1       2       3 ...
1          3       4  
2          2       3       4  
3      4
4      3       4       5
5
...

[D.J. Quavern]

Piet Souris wrote:It has nothing to do with having these zeroes or not. Having them, like I do, just makes it a little more convenient for me. And it works for repeated sequences just as well. Here's an example of repeated sequences, without zeroes, and just keeping in mind these two rules:

1) if the characters match, then the value = 1 + value left above. If that value happens to be outside of the table, then take 0.
2) else take the maximum of the value left and the value above. Again, if either of these are outside the table, take 0 for such a value.

Let the strings be "abcd" and "abcdabcd". Then, without zeroes, we get this table
      a   b   c   d   a   b   c   d
a    1   1   1   1   1   1   1   1
b    1   2   2   2   2   2   2   2
c    1   2   3   3   3   3   3   3
d    1   2   3   4   4   4   4   4

Take the first row. We start with (a, a). These are equal, so we get the value = 1 + value left above. Now, that value is outside the table, so we take 0 and we get 1.
Stil on the first row, for the letters b, c, and d we get that we take the max of the values left and above. But since the values above are outside the table, we take 0, and so all the three values are 1. Next we get again (a, a). We apply the formula: 1 + value left above = 1 + outside the table = 1 + 0 = 1. Et cetera.
The fourth row: we start with (d, a), unequal, so we take the max of left and above, so 1. The same holds for (d,b) and (d, c): taking the max of the values left and above. Then we get (d,d). Equal, so we take 1 + value left above = 1 + 3 = 4. Et cetera. The last value is again (d, d) = 1 + 3 = 4. Done, without the zeroes and with repeats!

And don't worry: DP has nothing to do with BITs!

Hello Piet!

I don't get how you analyzed the Hydra DP part, so I need to get back to you later on that, when I have processed it.

About the no zero solution, this is what I tried to do with my first code with having max of 0 and -1 in the indices, to make sure I don't select outside of my table.

           longuest_com_seq[row][col] = longuest_com_seq[max(0, row - 1)][max(0, col - 1)] + 1

But I do not get it right. I always got a letter too many on a repeating sequence of length 2, two too many on a repating sequence of length 3.... You get me!

[Piet Souris]

hi DJ,

then we have found our culprit!

Lets look at the first row of the table I gave in my previous post. We had this row:

   a   b   c   d   a ...
a  1   1   1   1

When we come to the second (a, a), lcs[0][4], we see equality, so we apply the formula: 1 + value left above. The value "left above" is at position [-1][3].
What I do is that I notice that the indices are invalid, so I take as value: 0, and as a result my second (a, a) becomes 1 + 0 = 0.

But you get a 2 instead. That is because you are minimizing your indices to 0. Sp your reasoning is:

(a, a) = 1 + lcs[-1][3]
      = 1 + lcs[0][3]   (0 = max(0, -1))
      = 1 + 1
      = 2

[D.J. Quavern]

Piet Souris wrote:hi DJ,

then we have found our culprit!

Lets look at the first row of the table I gave in my previous post. We had this row:

   a   b   c   d   a ...
a  1   1   1   1

When we come to the second (a, a), lcs[0][4], we see equality, so we apply the formula: 1 + value left above. The value "left above" is at position [-1][3].
What I do is that I notice that the indices are invalid, so I take as value: 0, and as a result my second (a, a) becomes 1 + 0 = 0.

But you get a 2 instead. That is because you are minimizing your indices to 0. Sp your reasoning is:

(a, a) = 1 + lcs[-1][3]
      = 1 + lcs[0][3]   (0 = max(0, -1))
      = 1 + 1
      = 2

Thank you for that. And again, sorry for the late reply! It's a busy time :/.
Now to the hydra!

Here is a way to do the Heads and Tails with DP. For this, we put the number of heads horizontally and the number of tails vertically. And we translate the rules into some formulas (like we have done sofar in DP). If (h, t) denotes the number of moves to target when we have h heads and t tails, we get these formulas:

(h + 2, t)      = 1 + (h, t)
(h - 1, t + 2)  = 1 + (h, t)
(h, t - 1)      = 1 + (h, t)

provided the indices left are within the table (i.e. >= 0)

We start  with (0, 0) = 0. From this we get that (2, 0), (-1, 2) and (0, -1) have a value of 1, but the last two are invalid. Having set a 1 in (2, 0), we put a circle around the 0 of (0,0) so that we can see that we have processed (0, 0).
Next, from (2, 0) we get (4, 0) = 2 and (1, 2) = 2. We  encircle (2, 0) and go on processing (4, 0) and (2, 0). Et cetera!
We get this table:

  h    0   1   2   3   4   5   6 ...
t
0      0       1       2       3 ...
1          3       4  
2          2       3       4  
3      4
4      3       4       5
5
...

Yes, I can visualise it now!
But how does the dynamic table knows 1. when it should stop? Our reply in the other case lie in the array at longuest_common_subsequence[alphabet.len -1][word.len -1], but here, how do we know it stops?
2. you wrote those rules:
(h + 2, t)      = 1 + (h, t)
(h - 1, t + 2)  = 1 + (h, t)
(h, t - 1)      = 1 + (h, t)

So you mean we apply just usual if statements and jump forward when one of the rule match?

[Piet Souris]

hi DJ,

well, the 'table' doesn't know when to stop! Indeed, you could have infinite number of Heads and half that number of tails!

So, it is up tou you when to stop, but most likely is when you have reached the requested (heads, tails).

And there are two ways to calculate the matrix.

If you come to location (h, t), then the value is either (h + 2, t) - 1, or (h - 1, t + 2) - 1, or (h, t - 1) - 1,
if these are legal values, or leave the cell blank. But I do not like this method. Foremost since a fixed size array is not quite suitable.

A much more flexible way is to a HashMap<someClass, Integer> where someclass is a class that contains two integer values (the row and column, for instance a Point), and the Integer is the number of moves to target.

I described how I would do this using DP in this post: head & tails

But since all this is quite some work, I would not use DP for this exercise.

[D.J. Quavern]

I think I understand. It took quite some time

But if I made a table, would it make sense to make a big one the first time, and then cache it for the next tests?

I would just need then to pick up the number of modes by looking at number of head (row) and number of tails (column) in my table.

[Piet Souris]

hi DJ,

wel, it dependsa little on how the method to implement is worded. Suppose the method you must implement is:

public static int solution(int heads, int tails)

then it would be a bit tedious to determine that table every time this method is invoked. In that case it might be a lot faster to compute the solution directly.
On the other hand: if the method is:

public static int[] solution(int[][] headsAndTails)

then it certainly makes sense to calculate that table, up to the maximum number of heads, and the maximum number of tails.

So, whether to use it or not, up to you. Is there a simple alternative to DP, as is the case here? And if so, do you use DP nevertheless, since it is always good for practice?

[D.J. Quavern]

I gess it's a good exercice, I will save it for later

[Piet Souris]

Sure do! In the meanwhile, I had a lot of fun and since I had forgotten all I once knew about DP, you certainly made me practise and rehearse and Google a lot!  But that is not a bad thing at my age.