dynamic-programming

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 is trivial. This single estimate decides feasibility.
• Integer or discretizable data. Pseudo-polynomial DPs (knapsack-style) need integer resource values. If weights/durations are floats, ask what scaling factor is acceptable and what error bound the user needs.
• Value only, or solution too. Recovering the optimal solution costs either full-table memory (parent pointers) or extra recomputation (divide-and-conquer recovery). A bound inside branch-and-bound often needs only the value.
• Standalone or subroutine. A DP called once can afford O(n²) time. A pricing DP called thousands of times inside column generation, or a bound called millions of times inside branch-and-bound, must be lean and warm-startable.
• Acyclic structure. Is there a natural stage ordering (items, periods, nodes of a DAG)? Cyclic state graphs need label-correcting/label-setting treatment or a resource that strictly increases along every transition to guarantee termination.
• Memory budget. A 2D table of 10^8 float64 entries is 800 MB. Decide early whether rolling arrays (value only) suffice or whether full recovery is required.
• Exactness requirement. If the exact state space is too large, is an approximation acceptable? Profit-scaling FPTAS for knapsack (Ibarra & Kim 1975), state-space relaxation for routing, or coarser time discretization all trade accuracy for size — but change what you can claim about the answer.
• One run or a family of runs. If the user will re-solve with slightly different data (duals changing each pricing iteration, capacities varying), structure the code so the instance-independent parts (graph construction, sorting) are reused.
• Python performance ceiling. Pure-Python nested loops handle ~10^6–10^7 state transitions per second; numpy-vectorized inner loops reach 10^8–10^9. Estimate transition count and pick the implementation style accordingly.
• Validation oracle. What independent check exists? Brute-force enumeration up to n≈15–20, a MIP model of the same problem, or known optima from a benchmark library. Plan the cross-check before trusting any DP.