DeepDP: Automated Synthesis of Recurrences for Dynamic Programming Problems

Dynamic programming (DP) solves many problems efficiently once an appropriate recurrence is known, but discovering that recurrence is often the key algorithmic step. We ask whether this process can be reversed: can small DP tables, constructed by solving each state independently through exhaustive search, provide enough evidence to recover a recurrence that scales to larger instances? We present DeepDP, which learns a structural prior from synthetic executable rules, represents recurrences through typed DP components, and adapts to new tasks using only table-reconstruction feedback, without target recurrence labels. Across 26 held-out tasks spanning four DP geometries, with target recurrence behaviors excluded from the training rule banks, DEEPDP achieves full functional generalization and improves mean accuracy by up to 49.11 percentage points over program-synthesis and symbolic baselines in the low-information regime. These results show that small exact computations can support the discovery of interpretable, executable algorithmic structure.