Unit 4: Basic Dynamic Programming

I. Foundations of Dynamic Programming

Dynamic Programming (DP) is an algorithmic technique for solving a problem by breaking it into smaller subproblems, solving each distinct subproblem once, and storing its result for reuse. It is especially effective when a recursive formulation repeatedly reaches the same smaller inputs.

• Central idea: A solution is built from previously computed solutions; for example, if dp[i] stores the answer for size i, then an answer for i + 1 can often be derived from one or more earlier dp values.
• Problem form: DP usually begins with a recurrence relation, such as F(n) = F(n-1) + F(n-2).
• Stored results: Results are saved in an array, table, map, or recursion cache so that no subproblem is solved repeatedly.
• Typical requirements: A problem is suitable for DP when it has overlapping subproblems and optimal substructure.
• Main objective: DP trades limited memory, often O(n) or O(n^2), for a major reduction in running time.

A. Introduction to Dynamic Programming

Dynamic Programming converts an inefficient recursive solution into an efficient solution by remembering answers to subproblems.

• Recursive starting point: Many DP problems have a natural recursive definition.
  
  TEXT

    answer(n) = combination of answer(smaller inputs)

  • n: The current problem size, index, position, capacity, or remaining target.
  • Smaller inputs: States that are closer to a base case.
• Avoiding recomputation: In naive Fibonacci recursion, F(3) is computed multiple times while evaluating F(5); DP computes F(3) once.
• Base cases: Every DP solution needs directly known values, such as F(0) = 0 and F(1) = 1.
• State storage: A one-dimensional array is suitable when the answer depends on one variable; a two-dimensional table is used when two variables define the subproblem, such as position and remaining capacity.

II. Recurrence-Based Counting Problems

Counting problems are common introductory DP applications because each answer can be expressed as the sum of valid ways to reach smaller states.

A. Fibonacci Sequence

The Fibonacci sequence demonstrates how DP eliminates duplicated recursive calls.

• Definition: Each term after the first two is the sum of its two immediate predecessors.
  
  TEXT

    F(0) = 0
    F(1) = 1
    F(n) = F(n - 1) + F(n - 2), for n >= 2

  • F(n): The nth Fibonacci number.
  • n: A non-negative integer index.
• Naive recursion cost: Direct recursion branches into two calls at each level, producing approximately O(2^n) time.
• DP observation: Only the states F(0), F(1), ..., F(n) are distinct, so there are only n + 1 subproblems.
• Worked example: To compute F(6), use:
  
  TEXT

    F(2)=1, F(3)=2, F(4)=3, F(5)=5, F(6)=8

  
  The result is 8.
• Space optimization: Since F(n) depends only on two earlier values, an array can be replaced by two variables.
  
  TEXT

    previous = 0
    current = 1
    repeat n times:
        next = previous + current
        previous = current
        current = next

  • Time complexity: O(n).
  • Space complexity: O(1) after optimization.

B. Tiling problem

The tiling problem counts the ways to cover a board using tiles of fixed shapes.

• Standard form: Count ways to tile a 2 x n board using 2 x 1 dominoes, placed vertically or horizontally.
• State definition: Let dp[n] be the number of ways to tile a 2 x n board completely.
• Last-tile analysis: The final placement has exactly two valid forms:
  1. Vertical domino: It fills the last column, leaving a 2 x (n-1) board; this contributes dp[n-1].
  2. Two horizontal dominoes: They fill the final two columns, leaving a 2 x (n-2) board; this contributes dp[n-2].
• Transition:
  
  TEXT

    dp[n] = dp[n - 1] + dp[n - 2]

  • dp[n-1]: Arrangements ending with one vertical domino.
  • dp[n-2]: Arrangements ending with a horizontal pair.
• Base cases:
  
  TEXT

    dp[0] = 1
    dp[1] = 1

  
  dp[0] = 1 represents one empty arrangement and makes the recurrence consistent.
• Worked example: For n = 4:
  
  TEXT

    dp[2] = 2
    dp[3] = 3
    dp[4] = 5

  
  There are five complete tilings of a 2 x 4 board.

C. Climbing Stairs

The climbing-stairs problem counts the possible ways to reach a stair when each move has limited size.

• Problem rule: A person may climb either one stair or two stairs in a single move.
• State definition: Let dp[i] be the number of distinct ways to reach stair i.
• Final-move reasoning: Every route to stair i must arrive:
  1. From stair i-1: By taking one step.
  2. From stair i-2: By taking two steps.
• Transition:
  
  TEXT

    dp[i] = dp[i - 1] + dp[i - 2]

• Base cases:
  
  TEXT

    dp[0] = 1
    dp[1] = 1

  • dp[0] = 1: There is one way to remain at the ground level: take no steps.
  • dp[1] = 1: The only route is one step of size 1.
• Worked example: For n = 3, the valid sequences are:
  
  TEXT

    1 + 1 + 1
    1 + 2
    2 + 1

  
  Therefore, dp[3] = 3.
• Connection to Fibonacci: The recurrence is Fibonacci-like, but indexing may differ because climbing stairs usually treats dp[0] as 1.

III. Core Properties of Dynamic Programming

DP works because subproblems repeat and because complete solutions can be assembled from correct smaller solutions.

A. State Definition and State Transition

A DP state precisely describes a subproblem, while a transition specifies how to compute that state from earlier states.

• State definition: A state must contain all information needed to determine the answer for one subproblem.
  
  TEXT

    dp[i] = number of ways to reach stair i

  • Index i: Identifies the current stair.
  • Value dp[i]: Stores the answer, not the sequence of moves.
• State transition: The transition expresses the dependency between states.
  
  TEXT

    dp[i] = dp[i - 1] + dp[i - 2]

• Transition direction: Dependencies must be computed before the current state; for increasing stair indices, fill dp[0] through dp[n].
• State completeness: If a decision depends on two quantities, both must appear in the state. For example, dp[i][sum] may represent whether a sum is possible using the first i elements.
• Common mistake: Defining dp[i] without explaining what it represents leads to transitions that may be mathematically correct-looking but logically invalid.

B. Optimal Substructure Property

Optimal substructure means that an optimal solution to a larger problem contains optimal solutions to its smaller subproblems.

• Principle: If a best answer for state S uses a smaller state T, then the solution chosen for T must also be best for T.
• Minimization example: If cost[i] is the minimum cost to reach position i, then:
  
  TEXT

    cost[i] = min(cost[i - 1], cost[i - 2]) + fee[i]

  • fee[i]: Cost paid upon reaching position i.
  • min(...): Selects the cheaper valid predecessor.
• Why it matters: Replacing a non-optimal subsolution with a better one would improve the whole solution, contradicting the claim that the whole solution was optimal.
• Counting distinction: In Fibonacci, tiling, and climbing stairs, DP counts all valid solutions rather than choosing one optimal solution. The same state-and-transition method still applies.
• Limitation: A greedy choice is not automatically justified by optimal substructure; DP considers all necessary prior states before selecting or combining results.

C. Overlapping Subproblems Property

Overlapping subproblems occur when the same smaller subproblem appears repeatedly during recursive computation.

• Fibonacci example: Calculating F(5) recursively evaluates F(3) through both F(4) and F(3) branches.
  
  TEXT

    F(5)
    ├── F(4) -> F(3) + F(2)
    └── F(3)

• Repeated work: Naive recursion recomputes F(3), F(2), and lower terms many times.
• DP remedy: Store F(3) after its first computation; all later requests read the stored value.
• Complexity effect: Fibonacci changes from exponential recursive growth to linear work:
  
  TEXT

    Naive recursion: approximately O(2^n)
    Dynamic programming: O(n)

• Not every recursive problem qualifies: Binary search has recursive calls but does not repeatedly solve the same subranges, so DP provides little benefit there.

IV. Building Dynamic Programming Solutions

A reliable DP solution follows a structured design process and then chooses either top-down or bottom-up evaluation.

A. Tabulation vs Memoizatation

Tabulation and memoizatation both store subproblem answers, but they compute states in different orders.

• 1. Tabulation: A bottom-up method that starts from base cases and fills a table iteratively.
  
  TEXT

    dp[0] = 0
    dp[1] = 1
    for i = 2 to n:
        dp[i] = dp[i - 1] + dp[i - 2]

  • Evaluation order: Smallest states to largest state.
  • Advantages: Avoids recursion-stack limits and usually has low overhead.
  • Limitation: May compute states that the final answer never needs.
• 2. Memoizatation: A top-down method that uses recursion and caches computed answers.
  
  TEXT

    solve(n):
        if n <= 1: return n
        if memo[n] exists: return memo[n]
        memo[n] = solve(n - 1) + solve(n - 2)
        return memo[n]

  • Evaluation order: Begins with the requested state and computes dependencies only when needed.
  • Advantages: Closely follows the recurrence and can avoid irrelevant states.
  • Limitation: Deep recursion can cause stack overflow for large inputs.
• Shared result: For Fibonacci, both methods take O(n) time and normally O(n) storage.

B. Dynamic Programming Process and Techniques

A systematic process prevents incorrect states, transitions, and base cases.

• 1. Identify the decision or quantity: Determine whether the problem asks for a count, minimum, maximum, feasibility result, or optimal value.
  • Example: Climbing stairs asks for a count of valid move sequences.
• 2. Define the state: Write one exact sentence for dp[...].
  • Example: dp[i] is the number of ways to tile a 2 x i board.
• 3. Derive transitions: Analyze the final decision, first decision, or last component of a solution.
  • Example: A tiling ends with either a vertical domino or two horizontal dominoes.
• 4. Set base cases: Assign values for the smallest valid states before applying the recurrence.
  • Example: dp[0] = 1, dp[1] = 1.
• 5. Determine evaluation order: Ensure every state needed on the right side of a transition is already available.
• 6. Optimize storage: Retain only states needed in future calculations; Fibonacci needs only the previous two values.

C. Formulating Dynamic Programming Problems

Formulating a DP problem means translating a verbal problem statement into a precise state model, recurrence, and answer location.

• Input interpretation: Identify variable quantities and constraints, such as board width n, target stair n, or allowed steps {1, 2}.
• State sentence: Express the meaning before writing code.
  
  TEXT

    dp[i] = number of valid ways to reach position i

• Choice analysis: Classify all mutually exclusive final choices so that every valid solution is counted once.
  • For stairs: The last move is either size 1 or size 2.
• Recurrence construction:
  
  TEXT

    dp[i] = dp[i - 1] + dp[i - 2]

  
  This works because the two last-move categories are disjoint.
• Base-case validation: Check small values manually, such as dp[1] = 1 and dp[2] = 2.
• Answer extraction: Specify the final required state; for an n-stair problem, the answer is dp[n].
• Complexity analysis: For a one-dimensional table filled once:
  
  TEXT

    Time: O(n)
    Space: O(n), or O(1) when only recent states are retained