Thanks, it looks like I had forgotten how dynamic programming works, e.g. constructing from possibly all subproblem solutions rather than just some way of breaking into some disjoint union. In this case I guess for code optimization a "subproblem" needs to be defined. I'm not sure if just breaking the code into chunks works as I was imagining. Maybe optimal substructure applies to some graph-like model of computation but not the naive assumption I made on how this would work.
No comments yet.