## Dynamic Programming Seam Finder (Optional)¶

Optional Task

Implement `DynamicProgrammingSeamFinder`

Note

Completing this portion of the project is completely optional and is only worth a negligible amount of extra credit if you choose to attempt it. We will not ask TAs to be familiar with this version of seam carving.

In the real world, seam carving is implemented using a different approach called dynamic programming (DP). In fact, the original paper for seam carving described the algorithm using dynamic programming.

The dynamic programming approach works by starting from the leftmost column and working your way right, using the previous columns to help identify the best shortest paths, when removing a horizontal seam. The difference is that dynamic programming does not create a graph representation (vertices and edges) nor does it use a graph algorithm.

Info

Watch this clip by a former TA from 8:30 onwards to learn about the seam finding dynamic programming task.

How does dynamic programming solve the seam finding problem? Most of the runtime is spent generating the dynamic programming table (DP table):

- Initialize a 2-D
`double[picture.width()][picture.height()]`

array where each entry corresponds to a pixel coordinate in the picture and represents the total energy cost of the least-noticeable path from the left edge to the given pixel. - Fill out the leftmost column in the 2-D array, which is just the energy for each pixel.
- For each pixel in each of the remaining columns, determine the lowest-energy predecessor to the pixel: the minimum of its left-up, left-middle, and left-down neighbors. Compute the total energy cost to the current pixel by adding its energy to the total cost for the best predecessor.

To find the shortest horizontal path using this DP table, start from the right edge and add the y-value of each minimum-cost predecessor to a list. The result is a list of y-value from right to left. Finally, to get the coordinates from left to right, `Collections.reverse`

the list.

To find the shortest vertical path, the same process is followed as the horizontal path but in a vertical manner (starting from the bottom and going up).