Topic: Dynamic Programming

In a simple video game, a skydiver exits the plane at Y elevation above the ground and X horizontal distance from a target. Over each unit of elevation, the skydiver can adjust their equipment so that they either fall straight down or glide with the wind some horizontal distance. The horizontal distance $($which is always positive$)$is determined by the wind$--$the skydiver may choose to either glide or drop, but cannot take any kind of "partial" action. If the player chooses to "glide", they must move the full wind force distance horizontally AND they also descend one level. $$

The goal of the game is for the player to land precisely on the target. We aren't worried about vertical momentum$--$the game assumes that even if the player chooses "drop" every time, they are still decelerating safely.

Because the wind force at each elevation is pseudorandomly determined, it is possible for a player to encounter a scenario where no possible sequence of moves would result in landing on the target. This would be a very bad experience for the player! As the game designer, your job is to define a dynamic programming algorithm which can be used to detect whether victory is possible for a given sequence of wind forces.

After you have designed your algorithm, demonstrate it using Y$=6,$X$=10,$and six random wind forces between $1$and $10.$ There should be no actual programming and should be shown as a proof.

Your submission must include:

$$Your Bellman Equation

$$A description of your matrix of subproblem solutions

$$Where is the answer within your matrix?

$$Your example matrix with all cells filled out