Problem Statement: USA Computing Olympiad
Problem Solution: Contest Results
Problem Summary: Essentially the problem describes Bessie the cow traveling through a course consisting of N checkpoints visited in sequence. However, being lazy, Bessie decides to skip K checkpoints where K < N (She cannot skip the first and last checkpoints as well). We must find the minimum distance Bessie is required to run by skipping K checkpoints. In this case, the distances are computed as Manhattan distances where the distance from x to y would be represented as: |x1-x2| + |y1-y2|.
Question: The issue is I am having trouble wrapping my head around the dynamic programming solution (linked above). Could someone provide a through explanation of the steps in discovering such a dynamic programming solution as well? Thanks for the support!