As an example, let's examine the recursive calls of the knapsack solver. For brevity, this knapsack is to be filled using a list of three items where the weight is uniformly one and has a capacity of two. Since the backtracking algorithm walks through the list of items in order (and tries either to include or exclude a particular item), the knapsack solver can be seen as a function K that maps any items that are remaining as well as capacity remaining to a particular value:
Therefore, at the same level, the same input parameter leads to the same value and this is easy to cache. In the preceding diagram, the nodes marked by the rectangle are calculated at least twice. This example was taken from the GeeksforGeeks' article (https://www.geeksforgeeks.org/0-1-knapsack-problem-dp-10/) regarding the 0-1 knapsack problem.
Before anything else, we can now implement a different trait to the backtracking:
pub trait DynamicProgramming {
fn fill(&...
