Day 8. This problem requires knowledge of dynamic programming. This type of DP is called Ear DP because its algorithm appeared in the problem whose name is "Ears". Ear DP requires current position and situation. (situation is sometimes n l…