Depth-First-Search(DFS) vs Dynamic Programming(DP)

DFS is a searching algorithm that would go as far as possible before backtracking, and Dynamic Programming, referring to GeeksforGeeks, is an algorithmic paradigm that solves a given complex problem by breaking it into subproblems and stores the results of subproblems to avoid computing the same results again. What are connections do they share? Let me uncover this by a Leetcode problem: 494. Target Sum.

You are given a list of non-negative integers, a1, a2, ..., an, and a target, S. Now you have 2 symbols + and -. For each integer, you should choose one from + and - as its new symbol.
Find out how many ways to assign symbols to make sum of integers equal to target S. 

Example 1:

Input: nums is [1, 1, 1, 1, 1], S is 3. 
Output: 5 
Explanation: -1+1+1+1+1 = 3, +1-1+1+1+1 = 3, +1+1-1+1+1 = 3, +1+1+1-1+1 = 3, +1+1+1+1-1 = 3 
There are 5 ways to assign symbols to make the sum of nums be target 3.

Note:

The length of the given array is positive and will not exceed 20. The sum of elements in the given array will not exceed 1000. Your output answer is guaranteed to be fitted in a 32-bit integer.

The intuition behind this question is to add either + or - to each number. So the brute force way and also the most straightforward one is using DFS, i.e., we would try to add + until the last number; then check whether the sum equals to the target; then backtrack to the previous number and try -; and keep exhausting every possible combination. Here is the Python version:

nums,target = [1,1,1,1,1],3
ret = 0
def helper(ind=0,total=0):
    global ret,target
    # reach the end
    if ind == len(nums):
        ret += total == target
    else:
        # try '+' first
        helper(ind+1,total+nums[ind])
        # then try '-'
        helper(ind+1,total-nums[ind])
helper()
print(ret)

We solved it, now what? As I pointed it out earlier that, this solution literally exhausts all combinations. Could we optimize it? Yes! That’s when Dynamic Programming could help.

Let’s picture this question in this way: if we assign + to the first number, we would need to know the number of ways that the remaining numbers sum to target-nums[0]; if we assign - to the first number, we would need to know the number of ways that the remaining numbers sum to target+nums[0]. This same strategy applies to all others. In other words, the answer to this question would be the sum of (1) the number of ways that nums[1:] sum to target-nums[0], and (2) the number of ways that nums[1:] sum to target+nums[0]. In this case we have divide the problem into two subproblems and we also notice that it has the two properties that could lead to a DP solution:

  • Overlapping Subproblems
  • Optimal Substructures

The Python code is:

nums,target = [1,1,1,1,1],3
def helper(ind=0,total=target):
    if ind == len(nums):
        return total == 0
    else:
        return helper(ind+1,total+nums[ind]) + helper(ind+1,total-nums[ind])
return helper()

This is one of the two ways of DP: top-down (the other is known as bottom-up). Now let’s add memorizations to avoid repeated computations. We can either use Python built-in functions or implement a table ourselves.

# use build-in packages
from functools import lru_cache

nums,target = [1,1,1,1,1],3
@lru_cache(None)
def helper(ind=0,total=target):
    if ind == len(nums):
        return total == 0
    else:
        return helper(ind+1,total+nums[ind]) + helper(ind+1,total-nums[find])

return helper()
# implement a dictionary to store results for subproblems
dp = {}
nums,target = [1,1,1,1,1],3
def helper(ind=0,total=target):
    if ind == len(nums):
        return total == 0
    elif (ind,total) in dp:
        return dp[(ind,total)]
    dp[(ind,total)] = helper(ind+1,total-nums[ind]) + helper(ind+1,total+nums[ind])
    return dp[(ind,total)]

return helper()

Bonus

There is another (smart) way of DP inspired by @lee215 that it solves it in bottom-up. This is a common solution to problems that need to generate permutations, like [Leetcode] 78. Subsets.

nums,target = [1,1,1,1,1],3
dp = {0:1} # initialization
for e in nums:
    new_dp = collections.defaultdict(int)
    for k,v in dp.items():
        new_dp[k-e] += v
        new_dp[k+e] += v
    dp = new_dp
return dp[target]

Summary

  • DFS exhausts all combinations.
  • Dynamic programming could use DFS to search subproblems so as to implement the top-down with memorization approach, therefore reduce the number of computations.

Feel free to leave a comment below!

Reference

https://www.geeksforgeeks.org/overlapping-subproblems-property-in-dynamic-programming-dp-1/

Subscribe
Notify of
guest
0 Comments
Inline Feedbacks
View all comments