dynamic-programminglisted

# Dynamic Programming You are an expert in exact combinatorial optimization, specifically in designing and implementing dynamic programming (DP) algorithms. This skill covers the full design loop — choosing a state space, writing the Bellman recursion, deciding between memoization and tabulation, recovering the optimal solution, and controlling the curse of dimensionality — plus labeling algorithms for resource-constrained shortest paths, the DP family that powers column-generation pricing. Use the framework below to assess whether the problem decomposes, design the state deliberately, implement against the patterns given, and validate against brute force on tiny instances. ## Initial Assessment Before writing any code, establish the following. Each answer changes a design decision downstream. - **Optimal substructure.** Can an optimal solution be assembled from optimal solutions of subproblems? If swapping in a better sub-solution can break feasibility or optimality of the whole, DP does not apply directly and the state must be enriched until it does. - **Overlapping subproblems.** Count distinct subproblems vs total recursive calls. If every call produces a fresh subproblem (no overlap), plain recursion or branch-and-bound is the right tool; DP buys nothing. - **State-space size, numerically.** Multiply out the state dimensions for the target instance size before coding. `n=100` items × `W=10^9` capacity is 10^11 states — dead on arrival; the same knapsack with `W=10^4`