liveBook · Manning

State transition formula

As explained in Algorithms Every Programmer Should Know

A recurrence that computes a problem state's value from values of other states.

Suppose you have a limited budget for cloud instances. At each step, should you buy the next instance or leave it behind? A state transition formula turns that choice into a lookup in a dynamic-programming table. T[i, j] is the best value available from the first i items with capacity j. The first row and column are zero: no items or no capacity means no value. section 7.1

If item i costs more than j, copy T[i−1, j]. Otherwise, compare skipping it with taking it: T[i, j] = max(T[i−1, j], vᵢ + T[i−1, j−wᵢ]). Here wᵢ is its cost and vᵢ its value. Both lookups use the previous row, so the same item cannot be taken twice. section 7.1

One cell, two choices

For an item costing 2 with value 3, T[2, 3] compares skipping (T[1, 3] = 2) with taking (3 + T[1, 1] = 5). Record 5. section 7.1

Figure 7.3 Visualization of the math used to evaluate cell T[2, 3] (circled in green) on the second row (w2 = 2, v2 = 3). The algorithm resolves a binary choice by executing a maximum value comparison between two paths. The exclusion path inherits the value directly above (T[1, 3] = 2). The active inclusion path accepts the new instance's throughput value (v2 = 3, highlighted in the red solid box) and subtracts its weight from the current capacity (3 - 2 = 1), forcing a pointer lookup to the previous row at column 1 (T[1, 1] = 2, highlighted by the red dotted circle). The combined value of 5 outperforms the exclusion path, updating the cell state.

Follow the two lookups from T[2, 3] to see how the winning value is calculated. section 7.1

How Algorithms Every Programmer Should Know covers it

How deep it goes
Works through boundary values and skip-or-take lookups, then gives pseudocode and a Python implementation.
Examples
Compares two choices at T[2, 3] and shows a completed table whose final value is 11.
What it assumes
Introduces table-cell meanings and zero-value boundaries before applying the recurrence.
What you can do after
Build it from scratch by filling a 0/1 knapsack table from boundary cells through each item and capacity.
How it connects
Links dynamic programming, 0/1 knapsack, two-dimensional tables, and capacity constraints.

This explainer was generated by Manning's knowledge graph from the text of Algorithms Every Programmer Should Know. The section links point to the parts of the book it draws on.