Stage 5: Data structures and algorithms, lesson 5 of 5

Dynamic programming

Advanced3 min readall versions
Explain it forThe essentials plus production detail and pitfalls.

Dynamic programming (DP) solves problems made of overlapping subproblems with optimal substructure: the best answer is built from the best answers to smaller versions of the same problem.

Two styles:

  • Top-down (memoisation): write the recursion and cache results in a map or array.
  • Bottom-up (tabulation): fill a table from the smallest cases upward, often using less memory.

A recipe that works for most DP problems:

  1. Define the state: what does dp[i] mean?
  2. Write the transition: how does dp[i] depend on smaller states?
  3. Set the base cases.
  4. Decide the order to fill the table, and where the answer ends up.

Classics: climbing stairs, coin change, longest common subsequence, 0/1 knapsack and edit distance.

Example

Java
// Coin change: the fewest coins that make an amount (bottom-up)
static int minCoins(int[] coins, int amount) {
    int[] dp = new int[amount + 1];              // dp[a] = fewest coins for amount a
    Arrays.fill(dp, Integer.MAX_VALUE);
    dp[0] = 0;
    for (int a = 1; a <= amount; a++) {
        for (int c : coins) {
            if (c <= a && dp[a - c] != Integer.MAX_VALUE) {
                dp[a] = Math.min(dp[a], dp[a - c] + 1);
            }
        }
    }
    return dp[amount] == Integer.MAX_VALUE ? -1 : dp[amount];
}

// Longest common subsequence of two strings
static int lcs(String x, String y) {
    int[][] dp = new int[x.length() + 1][y.length() + 1];
    for (int i = 1; i <= x.length(); i++)
        for (int j = 1; j <= y.length(); j++)
            dp[i][j] = x.charAt(i - 1) == y.charAt(j - 1)
                ? dp[i - 1][j - 1] + 1
                : Math.max(dp[i - 1][j], dp[i][j - 1]);
    return dp[x.length()][y.length()];
}

System.out.println(minCoins(new int[]{1, 2, 5, 10}, 27));   // 4 (10 + 10 + 5 + 2)
System.out.println(lcs("spring", "string"));                 // 5 ("sring")

Common mistake

Jumping straight to a table before defining exactly what each cell means. A precise state definition is most of the solution.

Under the hood

Many DP tables only need the previous row, which cuts space from O(n·m) to O(m). Greedy choices (always take the biggest coin) are faster but only correct for some coin systems; DP is correct for all of them. In interviews, start with the brute-force recursion, spot repeated calls, add memoisation, then convert to bottom-up if asked.

Check yourself

What makes DP faster than plain recursion?

How this connects

Where this leads

You've reached the end of this thread. Try a learning path for what's next.

Part of Crack the Java interview.

Was this lesson helpful?

Finished reading? Mark it complete to track your progress.