Pseudo-Polynomial Dynamic Programming is about Compression

Pseudo-polynomial dynamic programming has two opposite movements.

First, it compresses a large combinatorial search space into a table of states. For knapsack, brute force asks which of the subsets should be chosen. The dynamic programme instead keeps a table entry : after considering the first items, what is the best value at capacity ?

Many different subsets can lead to the same state . Once they do, the algorithm forgets the histories and keeps only the best value.

That is the compression: many histories collapse into one table entry.

The Expansion

The second movement goes in the other direction. The state coordinate ranges over every capacity value .

If is stored in binary, then the input contains only bits for this capacity. But the table has columns. In other words, one compact field expands into a unary-sized interval of states:

So pseudo-polynomial DP compresses the combinatorial part while expanding the numeric part.

The Point

For knapsack, dynamic programming replaces the brute-force search space by a table of size roughly . For Bi Knapsack, the table becomes with size .

This can be a real compression of the subset search. But it is not necessarily ordinary polynomial time, because the numeric dimensions may be exponentially larger than their binary encodings.

Therefore, pseudo-polynomial dynamic programming compresses histories into states, but may expand compact numeric inputs into unary-sized table dimensions.