We consider so-called ``incremental'' dynamic
programming algorithms, and are interested in the number of subproblems produced by them. The classical dynamic programming algorithm for the n-dimensional Knapsack problem is incremental, produces nK subproblems and nK^2 relations (wires) between the subproblems,
where K is the capacity of the knapsack. We show that any incremental algorithm for this problem must produce about nK subproblems, and that about nK\log K wires (relations between
subproblems) are necessary. We also give upper and lower bounds on the number of subproblems needed to approximate the knapsack problem.

Added upper and lower bounds for dynamic branching programs approximating the Knapsack problem (Section 5).

We consider so-called ``incremental'' dynamic programming (DP) algorithms, and are interested in the number of subproblems produced by them. The standard DP algorithm for the n-dimensional Knapsack problem is incremental, and produces nK subproblems, where K is the capacity of the knapsack. We show that any incremental algorithm for this problem must produce about nK subproblems.