Dynamic Programming: An induction approach

Here ‘u’ and ‘v’ are indexes.In the image above, we know that the shortest path from the top-left corner (the blue cell) to the [u, v] cell is 100..Likewise, the shortest path from the top-left corner to the cell [u+1, v] is 120 and the one in [u, v+1] is 115..You are probably wondering HOW we got these numbers..For now just assume we magically have them (ie, that is our induction hypothesis)..Well, in order to find the shortest path to the cell [u+1, v+1] we only have 2 options: either the path is coming from above (ie, from cell [u, v+1]) or from the left (ie, from cell [u+1, v]) because we only allow moves from left to right and from top to bottom..We know both the shortest paths from the cell above and from the cell on the left (115 and 120)..Therefore, we just need to choose the one that has the shortest path so far (115) and sum the value of the cell [u+1, v+1] itself..That yields us that the shortest path from the top-left corner to cell [u+1, v+1] is 115 + grid[u+1, v+1]..We can mathematically equate the above:shortestPath[u+1][v+1] = min(shortestPath[u][v+1], shortestPath[u+1][v]) + grid[u+1][v+1]We have our recursive formula that step 1 requires..Now, let’s go to step 2, ie, find the happy cases.Notice that shortestPath[0, 0] = grid[0, 0] (you started in the top-left corner and arrived in the top-left corner. Therefore the cost is only the value of ‘grid’ in that coordinate).shortestPath[0][0] = grid[0][0];We can now calculate the value of shortestPath[0, 1]..Since we are in the top of the grid, the only way to arrive in cell [0, 1] is from cell [0, 0]..Therefore shortestPath[0, 1] = shortestPath[0, 0] + grid[0, 1] = 5 + 3 = 8.. More details

Leave a Reply