[MUSIC] We are now ready to learn how dynamic programming algorithms work for finding optimal paths in the graphs. Let's start from this graph. And let's try to figure out how to move in this graph to reach their sink with the maximum number of attractions. At every step, there are only two decisions to make. Either to move vertically or move horizontally, south or east. So, to arrive to the final destination we can either arrive by moving south or moving east. And let's define a variable, which is SouthOrEast(i,j) as the length of the longest path from the initial node node (0,0) to node (i,j) in the grid. And, of course, we can immediately write a simple recursive program for computing south or east for (n,m), for the final destination vertex. It is simply the minimum of SouthOrEast of (n-1,m) plus the weight of the vertical edge into the final node. Or SouthOrEast(n,m-1) + weight of horizontal edge into the final node. And as soon as we analyzed it, there is a very simple recursive algorithm for computing the optimal path. To node (i,j) and the algorithm is called SouthOrEast and the only thing this algorithm does, is to compute alternatives between two scenarios. Moving to node (i,j) using the vertical edge or using to node (i,j) using the horizontal edge. Using this algorithm will solve our problem. If you watch me when I explain the change problem, you will figure out that this algorithm, while being correct, will take enormous time to finish. Because we will be making recursive calls many, many times, for a fixed value of i and j. And therefore, we need to come up with something better, and let's try to apply the dynamic program idea for traveling in this grid. Well, the optimal pass to reach node zero, of course we will see only zero attractions, so the score in this node will be zero The score in this node will be 1 because there is only one way to reach this node by moving vertically. The optimal score to reach this node will be 5, which is 1 plus 4, because there is no other alternative. And as a result, we can compute all values we described the lengths of the longest path. For the first row and the first column on this graph. Now something interesting starts. What is the best way to reach this node in the graph, the node (1,1). Should we move to this node using horizontal or vertical? South or east? Well, if we move horizontally into this node, then the length of the path will be 1 plus 3, and if we move vertically, the length of the path will be 3 plus 0. Of course, we choose to move horizontally, because 1 plus 3 is larger than 3 plus 0. And we know afterwards that the optimal path to this node has length 4. And for the future, we represent the edge horizontal edge that we use, to reach this node, as the bold edge, and we will see later why it is important. How about this edge? The same argument, and we decide to move to this node by using a vertical edge in this case. And we'll continue further and further. Let us try one more time. What about this node? How should we arrive to this node? In this case we compare, 4 plus 2 with 5 plus 2. 5 plus 2 is larger than 4 plus 2 and therefore, we choose to arrive to this node by moving along vertical edge. Therefore, the recurrence for computing the longest paths is the following. We define S(i,j) as the length of the longest path from the initial node to (i,j), and S(i,j) is simply the maximum of S(i-1,j) + the weight of the vertical edge or S(i,j-1) + the weight of the horizontal edge. And after we finish this, then in the programming procedure, we will fill the value of longest paths for every node and we'll learn that the optimal path to the final destination has length 34. When we are doing this, please note that in some cases, instead of making decision South or East, we will make a decision South and East. For example, in this particular node, we are comparing 22 plus 0, which is equal to 20 plus 2. Which means that both horizontal and vertical edges entering into this vertex are in bold. And now, I hope it will become clear why we were retaining information about both edges. Because 34, the number in the last node, tells us the length of the longest path. But it doesn't tell us how this longest path was traversing the graph. But with both edges, we can figure out because we know that we arrive to the last node marked by 34 by moving along a horizontal bold edge, here it is. We arrive in the node labeled by 32. Once again, by moving by horizontal edge, and we arrive to this node labeled by 30 by moving along a vertical edge. We continue backtracking in this way, and sooner or later, we will arrive in the initial node, and the blue path shown on the slide is actually an optimal path from the initial to the final destination in this graph. And we now move from describing how dynamic programming works in a simple Manhattan grid to describing how it works in arbitrary alignment graphs.