Back to course

Exercise 3

Dynamic Programming

Algorithm DesignRecurrence RelationsMedium Difficulty

Exam Format & Expectations

Dynamic Programming questions typically ask you to:

  1. Define subproblems - What does T[i] represent?
  2. Write recurrence relation - How to compute T[i] from smaller subproblems
  3. State base cases - When does the recursion stop?
  4. Explain the algorithm - One sentence description

Past Exam Example: Weighted Activity Selection (2024)

Problem:

Given activities A = { a1, ..., an } where each activity ai has:

  • Start time s(ai)
  • Finish time f(ai)
  • Profit p(ai)

Activities are sorted by finish time: f(a1) ≤ f(a2) ≤ ... ≤ f(an)

Subproblem: For 1 ≤ i ≤ n, let T[i] = maximum profit using activities from {a1,...,ai}that must include ai.

Give recursive formula for T[i]

Full Solution(10/10)

First, define the helper set:

endsBefore(ai) = { aj ∈ A | f(aj) < s(ai) }

(activities that finish before ai starts)

Recurrence Relation:
Base case: If endsBefore(ai) = ∅:
T[i] = p(ai)
Recurrence: If endsBefore(ai) ≠ ∅:
T[i] = p(ai) + maxa_j ∈ endsBefore(a_i) { T[j] }

Explanation: Since we must include ai, we get profit p(ai). We can also include the best compatible predecessor aj that ends before ai starts. If no activity can precede ai, then T[i] = p(ai).

Example: Optimal Word Breaking (2023 Resit)

Problem:

Given a string X = x1x2...xn of n characters. We have a function score(xi...xj) that returns the score of substring xi...xj as a potential word. Goal: Split X into words to maximize total score.

Example: "meetateight"

score("meet") = 10, score("at") = 3, score("eight") = 2
Split: "meet at eight" → total score = 15

Subproblem: For 0 ≤ i ≤ n, let T[i] = maximum total score for splitting x1...xi

Question 3a: Give recursive formula for T[i]

Full Solution(7/7)
Recurrence Relation:
Base case: T[0] = 0
(empty prefix has score 0)
Recurrence: For i > 0:
T[i] = max1≤j≤i { T[j-1] + score(xjxj+1...xi) }

Explanation: To find the best split of x1...xi, we try every possible last word xj...xi (for j = 1 to i). The total score is the score of this last word plus the optimal score for the remaining prefix x1...xj-1.

Question 3b: Algorithm to find the maximum score

Full Solution(3/3)
Word Breaking Algorithm
T[0] = 0 for i = 1 to n: T[i] = -∞ for j = 1 to i: T[i] = max(T[i], T[j-1] + score(X[j..i])) return T[n]

Time complexity: O(n²) assuming score() runs in O(1)

Common DP Patterns

Linear DP

T[i] depends on T[j] for j < i

  • • Longest increasing subsequence
  • • Word breaking
  • • Activity selection
  • • Maximum subarray sum

2D DP

T[i,j] depends on smaller subarrays

  • • Edit distance
  • • Matrix chain multiplication
  • • Knapsack problem
  • • Longest common subsequence

Grading Rubric

Point Breakdown

  1. 1

    Define subproblem (2-3 pts)

    Clear definition of T[i]

  2. 2

    Base case (1-2 pts)

    T[0] or smallest subproblem

  3. 3

    Recurrence (3-4 pts)

    Correct recursive formula

  4. 4

    Algorithm (2 pts)

    Implementation if asked

  5. 5

    Explain in one sentence

    "We try all possible..."

Common Mistakes

  • • Wrong subproblem: Missing information in state
  • • Index errors: Off-by-one, accessing T[-1]
  • • Missing cases: Forgetting "do nothing" option
  • • No explanation: Just formula without reasoning
  • • Wrong direction: max vs min confusion
Previous: Greedy ChoiceNext: Flow Algorithms