Identifying base cases

In the previous lesson we learned the conceptual picture of a base case and classified it into either a genuine or a boundary type. In this lesson, we done is turn that picture into a workflow we can apply to a specific recurrence. At this stage, we already have the concrete inputs from the Bellman equation, the transition function T(s, a), the action set A(s), the operator pair (opt, ⊕) and the problem statement itself for the genuine cases. The procedure to identify the base cases for a dynamic programming problem has the following four steps.

Step 1: Locate where the recurrence stops

The recurrence is defined for most states in the state space DAG, but every chain of transitions eventually reaches a state where the recurrence either has no smaller states to refer to, or refers to states outside the recurrence's domain. Those terminal states are the candidates for base cases, and we identify them by tracing the recurrence's transition function T(s, a).