Dynamic Programming by Example

Backtracking is a recursive method of performing a depth first search.  Each path is considered until the point it's known not to meet the solution criteria, then the algorithm backtracks to the last branch where the criteria is no longer violated and tries another sub-branch from there.  This proceeds until the solution is found or all possibilities have been exhausted.

Dynamic Programming can often provide considerable optimization by reducing pursuit of fruitless branches.

Examples:

Combination Sum

Given a set of positive integer possible values, find all combinations of them that sum to a positive integer target value.

Example
candidates: [2, 3, 6, 7]target: 7
answer: [[7], [2,2,3]]

Backtracking Solution (casual psuedo-code):

We're going to iterate over combinations of the candidate values until we hit one that sums to the target, then add that to the list of answers.  This follows a general pattern for backtracking algorithms.

 
   findSum(soFar: List[int], target: int):
      if sum(soFar) == target:#did we hit our target?
         answer.append(soFar)
         return
   
      for ii in range(start, n):
         soFar.append(candidates[ii]) #try out soFar w/ candidates[ii]
         findSum(soFar, target)
         soFar.pop() #remove candidates[ii]

#given target & candidates
##main(target, candidates)
n=len(candidates)
answer=[]
findSum([], target)
return answer
  

DP Solution (Python3):

Here we're going to build up the "soFar" list of candidates that sum to target.  Once we have all such "soFars" we'll return it.  However, to get there, we're first going to build up equivalent "soFar" lists for all of the target's complements on down to zero.  Again, here are the inputs:

candidates: [2, 3, 6, 7]
target: 7
answer: [[7], [2,2,3]]

Note the list below.  For 7's [2,2,3] for example, we could get there subtracting and using the result to lookup the complement's soFar: 7-3=4 => 4-2=2 => 2-2=0

[0] => []
[1] => []
[2] => [[2]]
[3] => [[3]]
[4] => [[2,2]]
[5] => [[2,3]]
[6] => [[2,2,2],[3,3], [6]]
[7] => [[2,2,3],[7]]

class Solution:
    def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:
        dp=[None for i in range(target+1)]
        dp[0]=[[]]
        
        #build up "soFar" not just for target but for all numbers 1 to target
        #use candidates and Targets' complements to find paths that add up
        for val in candidates:
            for tgt in range(val, target+1):
                tmp = [x + [val] for x in dp[tgt-val]] if dp[tgt-val]!=None else None
                if tmp!=None:
                    if dp[tgt]==None:
                        dp[tgt]=tmp
                    else:
                        dp[tgt]+= tmp
       
        return [] if dp[target]==None else dp[target]

Applying the Pattern

Now let's attempt to apply this pattern to another example.  We'll choose the well known and solved problem of sorting an array of values.  The goal here is not to achieve a rigorously defined solution, not even a functional one per se.  My purpose is to demonstrate the application of the Backtracking pattern and progression thereafter to a DP solution.  The code hereafter should serve primarily as an analog for comparison to the code above.

Backtracking

A backtracking approach would look something like this....We'll try every combination by adding the next available value to the end of the list and testing.  If it's not in order we backtrack and proceed to the next branch.  If it is in order we march forward.  We return the full list once we're done.

Now we're not setting aside performance for this exercise but it's worth noting this one is abysmal.  Each successive item in the input list launches an O(N-1) search for which each item in turn launches another O(N-2) search, etc. O(N!)

sort(start:int, soFar: List[int]):
      m=len(soFar)
      if soFar[m-1]>soFar[m-2]:
         if m==n:
            answer=soFar 
            return
      else:
         return
          
      for ii in range(start, n):         
         soFar.append(inputList[ii])
         findSum(start+1, soFar)
         soFar.pop() #remove inputList[ii]

#given inputList
##main(inputList)
n=len(inputList)
answer=[]
sort(0, [])
return answer

DP Solution

Here we're going to build up "soFar" by adding each value from the input to the answer.  Each subsequent operation will build upon the previous one so we avoid any redundant or unnecessary processing.  Since we know that our list input from prior steps is already sorted, we may choose to use a binary search to find the insertion point.

By progressively performing N binary searches on the list, we produce a sorted array in a single loop over the inputList. N binary searches at O(log(N)).  However, the insertion has to perform an O(N) reshuffle in addition to its log(N) binary search.  Our algorithm is thus O(N^2).

This is essentially an Insertion Sort algorithm.  Perhaps not competitive with canonical N log(N) sorting algorithms, nevertheless an improvement over O(N!)!  Moreover, simply by mechanically following the Dynamic Programming approach we've achieved our goal and unintentionally arrived at a well known sorting algorithm.

Insertion Sort
Bellman-Ford shortest path via DP