Dynamic Programming Problems

Dynamic programming is the highest-leverage skill in algorithmic interviews. Almost every "hard" problem is a DP problem dressed up. The reason DP feels hard is that it requires three skills at once: identifying the subproblem, defining the state precisely, and writing the transition equation. Master those three and the implementation — top-down with memoization or bottom-up with a table — falls out automatically.

Interview DP problems cluster into recognizable families. 1D DP (climbing stairs, house robber, longest increasing subsequence) — state is a single index. 2D DP (longest common subsequence, edit distance, unique paths) — state is two indices. Grid DP (minimum path sum, dungeon game) — state is (row, col). Knapsack (coin change, partition equal subset, target sum) — state is (item index, capacity). Interval DP (matrix chain multiplication, burst balloons) — state is (left, right). Bitmask DP (traveling salesman, partition to K equal subsets) — state encodes a subset.

The Ratta DP track covers the canonical interview set across all families: Climbing Stairs, House Robber I and II, Longest Palindromic Substring, Decode Ways, Coin Change, Maximum Product Subarray, Word Break, Longest Increasing Subsequence, Longest Common Subsequence, Unique Paths, Combination Sum IV, and Jump Game. Each problem includes both top-down and bottom-up implementations with explicit state and transition definitions, in C++, Java, Python, and Go.