Hands-On Data Structures and Algorithms with Rust

Dynamic programming

The concept of dynamic programming is one of these techniques that you thought had a different name: caching. The fundamental idea is to save relevant temporary results to a cache and use this precomputed result instead of recalculating something over and over again!

This means that a problem and a potential solution have to be examined to find relevant sub-problems, so any result can be cached. The main upside of this approach is that it finds the globally best solution possible, but at the price of a potentially high runtime complexity.