liveBook · Manning

Base case

As explained in Timeless Algorithms, The Foundational Ideas

A base case is a directly known computational state that requires no further recursive decomposition.

A base case is a known value at the boundary of a dynamic-programming problem. It anchors the recurrence: once the boundary values are defined, dependent states can be evaluated from smaller subproblems. States, transitions, and base cases must be specified together; a recurrence alone does not determine a complete solution. section 6.1.3 section 6.2.3

A base case can represent different kinds of boundaries:

  • A trivial subproblem, such as having no items or no remaining capacity. section 6.2.3
  • An initial value from which tabulation builds larger answers. section 6.3.3
  • A terminal condition, such as the end of a planning horizon or direct connections in a network. section 6.4.2 section 6.4.3

Coin change

For counting combinations, ways[0] = 1: there is one way to make zero, by selecting no coins. This initial count lets tabulation build counts for positive amounts; without it, later counts remain zero. section 6.3.3

ways[0]=1

The equation states the initial count used to build the coin-change table. section 6.3.3

How Timeless Algorithms, The Foundational Ideas covers it

How deep it goes
Defines boundary values and demonstrates their use in tabulation, while leaving their identification problem-dependent.
Examples
Uses zero-item and zero-capacity knapsack states, ways[0] = 1 for coin change, terminal inventory costs, and direct network routes.
What you can do after
Apply the concept by identifying and initializing known boundary states before evaluating dependent states.
How it connects
Links base cases to states, transitions, recurrence relations, and tabulation.

Also explained in

Compare how 2 books explain base case →

Related concepts

This explainer was generated by Manning's knowledge graph from the text of Timeless Algorithms, The Foundational Ideas. The section links point to the parts of the book it draws on.