Algorithms

Dynamic Programming

Цели урока

  • Understand the DP paradigm
  • Master the 5-step approach
  • Solve 1D and 2D problems
  • Optimize memory usage

Предварительные знания

  • Divide and Conquer
  • Divide and Conquer

90% of algorithm interview problems are solved with DP. It's not magic - it's a technique: define the state, write the recurrence, find the answer.

  • Autocorrect (edit distance)
  • Git diff (LCS)
  • Bioinformatics (sequence alignment)
  • Finance (optimal strategies)

Richard Bellman and a name chosen to hide the math

Dynamic programming was created by Richard Bellman at the RAND Corporation in the early 1950s. The name has a famous backstory that Bellman told in his autobiography. RAND worked for the Air Force, and the Secretary of Defense Charles Wilson had an open hostility to mathematical research. Bellman needed a label for his work on multistage decision processes that would not sound like math. He picked dynamic, because it sounded active and could not be used in a pejorative way, and programming, which at the time meant planning and scheduling rather than writing code. The core idea is the principle of optimality: an optimal solution is built from optimal solutions to its subproblems, and overlapping subproblems are solved once and stored. That insight unified a huge class of optimization problems, from shortest paths to inventory control.

Idea: Subproblems + Memoization

**Dynamic Programming (DP)** = breaking into subproblems + caching results.

0

1

Sign In

**DP solution:** cache already-computed values.

**DP vs D&C:** in D&C subproblems are independent. In DP subproblems overlap (one computes the same subproblem many times).

fib(50) with naive recursion takes ~2^50 ≈ 10^15 operations. With DP?

Approach to DP Problems

**Example: Coin Change**

**The main question:** 'What information is needed to make a decision?' That determines the state.

For the problem 'number of ways to make a sum with coins', what changes?

1D DP: Classics

**1. Climbing Stairs:**

**2. House Robber:**

**3. Longest Increasing Subsequence (LIS):**

House Robber: nums = [2, 7, 9, 3, 1]. Answer?

2D DP: Tables

**1. 0/1 Knapsack:**

**2. Longest Common Subsequence (LCS):**

**3. Edit Distance:**

**Memory optimization:** often you can store only 2 rows (current and previous) instead of the full table.

edit_distance("kitten", "sitting") = ?

Dynamic Programming

  • Subproblems + memoization
  • 5 steps: State, Recurrence, Base, Order, Answer
  • Top-down (recursion + memo) vs Bottom-up (table)
  • 1D: O(n), 2D: O(n×m)
  • Memory can often be optimized

Related Topics

DP is one of the main paradigms.

  • Greedy — When subproblems are independent
  • Divide & Conquer — Without overlapping subproblems

Связанные уроки

  • alg-19-divide-conquer — DP is divide and conquer with overlapping subproblems
  • alg-20-greedy — Greedy commits locally; DP explores all subproblems
  • alg-28-lcs — LCS is a canonical 2D DP application
  • alg-30-knapsack — Knapsack is the model DP optimization problem
  • la-09-systems — Bellman equations solve dynamic optimization via DP
  • comp-23-local-optimization
  • comp-25-loop-optimizations
  • plt-27-ir-optimization
  • ml-36-seq2seq
Dynamic Programming