DP Recurrence Relation Formulation

What is a Recurrence Relation?

You've already encountered a recurrence relation with the Fibonacci sequence:
$\text{Fib}(n)=\text{Fib}(n-1)+\text{Fib}(n-2)$
A recurrence relation in DP is an equation that defines the solution to a problem in terms of the solutions to its smaller, constituent subproblems. It always consists of two key parts:

1. The Recursive Step: The formula that relates the larger problem to smaller ones (e.g., Fib(n-1) + Fib(n-2)).
2. The Base Case(s): The smallest subproblems whose solutions are known directly, without needing further recursion (e.g., Fib(0) = 0, Fib(1) = 1). These prevent the recursion from going on forever.

A Systematic Approach to Formulating a Recurrence

Developing a recurrence relation isn't magic; it's a structured thought process. We can break it down into three steps, which we'll apply to every DP problem.

Step 1: Define Your Subproblem (The State)

Before you can write a formula, you must precisely define what you're trying to solve. This means defining a function, say DP(i, j, ...), and stating exactly what it calculates. The parameters i, j, ... represent the state of the subproblem. Getting this definition right is more than half the battle.

Step 2: Find the Transition (The Recursive Formula)

Once you've defined your subproblem, say DP(n), you need to figure out how to compute its value using the solutions to smaller subproblems (like DP(n-1), DP(k) where k < n, etc.).

A powerful mental trick here is to think about the last step or final choice that leads to the solution for DP(n).

• If the problem asks for a maximum or minimum value, you'll typically take the max or min over all possible last choices.
• If the problem asks to count the number of ways, you'll typically sum the results of all possible last choices.

This "last step" logic is what forms the recursive part of your relation.

Step 3: Determine the Base Cases

Your recurrence breaks down a problem into smaller and smaller pieces. The base cases are the smallest pieces whose answers are known trivially, without any further calculation. They are the "end points" of your recursion. For example, the number of ways to climb 0 stairs, or the minimum coins to make change for $0.

Let's put this three-step process into action with some examples.

Example 1: Climbing Stairs (A Counting Problem)

Let's start with a classic introductory problem.

Problem: You are climbing a staircase. It takes n steps to reach the top. Each time you can either climb 1 or 2 steps. In how many distinct ways can you climb to the top?

Let's apply our three-step process.

Let's summarize the logic from the article using our framework:

1. Define Subproblem: Let ways(i) be the number of distinct ways to climb to the i-th step. Our goal is to find ways(n).

2. Find Transition: To reach step i, what could have been our last move?

   • We could have taken a single step from i-1. The number of ways to get to i-1 is ways(i-1).
   • We could have taken two steps from i-2. The number of ways to get to i-2 is ways(i-2).
     Since these are mutually exclusive options, the total number of ways to reach step i is the sum of the two.
     Recurrence: ways(i) = ways(i-1) + ways(i-2)

3. Define Base Cases:

   • ways(1) = 1 (Only one way to get to the first step: a single 1-step).
   • ways(2) = 2 (Two ways to get to the second step: 1+1 or 2).

We have successfully formulated the recurrence relation for the climbing stairs problem!

Example 2: The Coin Change Problem (An Optimization Problem)

Now let's tackle a problem that involves finding a minimum value.

Problem: You are given an array of coin denominations coins and a total amount m. Find the minimum number of coins that you need to make up that amount. Assume an infinite supply of each coin.

This is a classic DP problem. Let's watch a video that derives the recurrence.

Let's recap the formulation from the video:

1. Define Subproblem: Let min_coins(m) be the minimum number of coins required to make the amount m. We want to find min_coins(target_amount).

2. Find Transition: To make change for amount m, what was the last coin we added? It could be any coin c from our set of coins. If the last coin we added was c, then before that, we must have had an amount of m-c, and we must have formed it with the minimum number of coins, which is min_coins(m-c).
   So, for each possible last coin c, the total number of coins would be 1 + min_coins(m-c).
   Since we want the overall minimum, we must try all possible last coins and choose the best option.
   Recurrence: min_coins(m) = 1 + min(min_coins(m - c)) for every coin c in coins where m >= c.

3. Define Base Case:

   • min_coins(0) = 0. It takes 0 coins to make an amount of 0.

Generalizing the Recurrence Relation

The process of defining the subproblem and then considering the "last choice" to form the transition is a universal technique in DP.

The video demonstrates a key idea: a good subproblem definition makes the transition logic almost naturally fall into place. If you're struggling to find the recurrence, you may need to revisit and redefine your subproblem, perhaps by adding another parameter to the state.

Conclusion

In this lesson, you've learned the most fundamental skill in dynamic programming: how to formulate a recurrence relation. This is the intellectual core of any DP solution.

Key Takeaways:

• A recurrence relation is the mathematical blueprint of a DP solution, consisting of a recursive step and base cases.
• A systematic, three-step approach is highly effective for formulation:
  1. Define the Subproblem (State): Clearly state what DP(...) computes.
  2. Find the Transition (Recurrence): Use the "last choice" logic to relate the problem to its subproblems. This usually involves a min, max, or sum operation.
  3. Determine the Base Cases: Identify the smallest subproblems that can be solved directly.

Up Next:
You now know how to identify a DP problem and how to write the recurrence relation for it. The next logical step is to turn that relation into code. In our next lesson, we will focus on the bottom-up (tabulation) approach. You'll learn how to systematically solve all subproblems from smallest to largest, storing the results in a table (like an array or a 2D list), which is a highly efficient and common technique in competitive programming.