From Recursion to Parallelization: Plug & Play Dynamic Programming
摘要
Dynamic Programming (DP) is fundamental to computational science education and application, traditionally taught through tabulation methods that emphasize manual loop construction. This paper introduces a modular, systematic plug-and-play framework that greatly simplifies DP algorithm design and parallelization. Our approach begins with a recursive divide-and-conquer analysis, decomposing DP into reusable components: Refactored Recursion (RR), OrderSpec, TileSpec, dp_solve, dp_tile_solve, and dag_run. These modules encapsulate recursive structures and facilitate seamless parallelization via dynamic Directed Acyclic Graph (DAG) scheduling. We demonstrate the versatility of this framework using three classical textbook problems: Longest Common Subsequence (LCS) highlights the plug-and-play simplicity, Matrix Chain Multiplication (MCM) employs transitive reduction for dependency clarity, and the Cut-Rod problem illustrates previously obscured tiling optimizations and parallel solutions. This new modular paradigm significantly reduces DP’s learning curve, shifting educational focus from code-centric methods to intuitive, reusable patterns, bridging theoretical recursion with practical implementations and greatly enhancing computational science education.