Overview

This section contains dynamic programming problems from Google interviews.

• Electoral Tie Analysis — Determine if an electoral tie is possible using subset sum, and identify must-win states.
• How Many Ways Can a Party Win — Count the number of subsets of states that yield a winning electoral vote total.
• Red Card, Black Card Game — Find the optimal stopping strategy and expected earnings in a card-drawing game.
• Swiss Gondolas — Maximize quality ratings over at most K consecutive gondolas using sliding window DP.
• The Jumping Game — Maximize points by choosing to take or skip values in an array, jumping forward by the taken value.
• Painting a Fence — Find the minimum brush strokes to paint planks of varying heights using vertical and horizontal strokes.
• Score Combinations in Football — Enumerate all ordered scoring sequences that produce a given football score.