Verifying base cases

In the previous lesson we learned a four step procedure to identify base cases for any dynamic programming problem which completes the recurrence for the algorithm. However a complete algorithm is not the same as a correct one. The base set could be complete but contain wrong values. The final step is to verify the base cases to ensure they are correct. 

In this lesson we will learn a verification procedure that takes the derived recurrence and pushes back against it systematically, surfacing any remaining mistakes while they are still cheap to fix.

1. The smallest-instance check

We compute dp(s) by hand for the smallest non-trivial state, a state that is not itself a base case, but whose immediate dependencies are all base cases and verify the result matches the obvious answer to that small instance.