The real hard part is solving the recursive backtracking problem.

Once we have the recurrences, it’s rather mechanical to convert backtracking into dynamic programming.

Indeed, we should also prove the optimal substructure property to show that the results we memoize are actually useful. But if we are in a time crunch simply assume this property holds.

Step 1. Find the Recurrence / Brute Force

This is the difficult part. Don’t proceed further until the correct recurrence is found.

If we are actually implementing a DP problem in code, implement the recurrence with brute force recursion first, make sure it’s correct by testing small inputs, then move on to the DP conversion step.

Otherwise it becomes impossible to debug.

Recurrence Examples

Step 2. Order of evaluation / Tabulation / Bottom Up

From the recurrence, we need to observe the parameters of:

1. The current function call: Determines where in the array should we assign value to
2. The recursive call(s): What value does the current call depend on
3. The initial call: What to return at the very end. This can be found from your working backtracking code, take the parameters from the first call.

• @EX Different Parameters

Then we can compare the parameters of the current call with the recursive calls to see the order.

• @EX Finding Order of Evaluation

Now we iterate over all possible combinations of backtracking parameters.

1-Dimensional case

No nested for loops. The DP data structure is likely an 1D array and the for loop goes in the order of evaluation.

N-Dimensional case