liveBook · Manning

Dynamic programming

As explained in Algorithms Every Programmer Should Know

An algorithm-design technique that solves overlapping subproblems and stores intermediate results to avoid repeated computation.

Suppose you have a fixed cloud budget and several server instances, each with a cost and a throughput value. Which combination gives the most throughput? Trying every include-or-skip combination becomes expensive as the list grows. Dynamic programming avoids repeating the same smaller calculations: record the best answer for each smaller budget and set of available instances, then reuse it. section 7.0 section 7.1

For 0/1 knapsack, build the answer from small cases upward:

  • Make a table with rows for how many items may be used and columns for capacities from zero through the budget. With no items or no capacity, the best value is zero. section 7.1
  • For each cell, ask: does the current item fit? If not, copy the answer from the row above. section 7.1
  • If it fits, compare skipping it with taking its value plus the previous row’s answer for the remaining capacity. Store the larger result. Looking at the previous row keeps the choice strictly 0/1. 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 for capacity 3 and the second item: skipping gives 2; taking gives 3 plus the earlier answer of 2, so the cell becomes 5. section 7.1

Finish a small capacity plan

Four instances cost 1, 2, 4, and 5 credits and provide values 2, 3, 5, and 6. At capacity 8, the final choice compares skipping the fourth instance, worth 10, with taking it and using the best value at the remaining capacity of 3: 6 + 5 = 11. The stored answer is 11. section 7.1

This table takes O(n × W) time and O(n × W) space for n items and capacity W. A one-dimensional array can reduce memory because each choice needs values from the preceding row, but the full table makes those dependencies easier to see. For divisible goods, fractional knapsack instead permits a greedy value-per-weight approach; do not assume that approach works when items cannot be split. section 7.3

The same habit—save answers to smaller cases and use them to improve larger ones—also appears in Floyd–Warshall. Its distance matrix compares the best known route between two vertices with a route through a newly considered intermediate vertex. Here the stored result is a shortest distance, not a maximum item value. section 9.1

How Algorithms Every Programmer Should Know covers it

How deep it goes
Works through table initialization, include-or-skip transitions, a completed knapsack result, and complexity; also sketches distance-matrix updates.
Examples
Traces four cloud instances across capacities up to eight and tests intermediate vertices in a four-node graph.
What it assumes
Assumes basic arrays and loops for implementation while introducing binary item choices, table states, and zero-value boundaries.
What you can do after
Build it from scratch as a 2D 0/1 knapsack table and evaluate its time and memory costs.
How it connects
Connects overlapping subproblems and optimal substructure to 0/1 knapsack, greedy algorithms, fractional knapsack, and Floyd–Warshall.

Also explained in

Compare how 8 books explain dynamic programming →

Related concepts

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.