Checkpoint method for choice recovery in dynamic programming.
Many dynamic programming algorithms consist of a 'forward pass' computation to optimize a cost function, followed by a 'choice recovery' computation to construct a configuration that optimizes the cost function. 'Checkpointing' is a method to perform choice recovery using limited storage. During a forward pass, checkpoints in an optimal configuration are identified. Then recursion is used to fill in the portions of an optimal configuration between successive checkpoints. Choosing the number of checkpoints to use mediates a tradeoff between storage and speed.
Algorithms↗