# Divide and Conquer, Dynamic Programming, and Backtracking

Divide and Conquer, Dynamic Programming and Backtracking are sledgehammers for a huge class of problems and at first glance, they seem to be similar since typically these algorithms involve a resursive process represented as a tree structure.

#### Deltas

The concept of Divide and Conquer is probably the most explicit among the three. It invovles a top-down process (e.g., merge sort):

- Divide the current problem into a number of non-overlapping subproblems
- Conquer each problem recursively
- Combine the solutions of the subproblems for the current problem.

Such recursive problem renders a **recurrence relation** (for both problem itself and computational complexity) and can be analyzed by Master theorem.

DP problems are actually a subset of Divide and Conquer problems: in general, DP methods are Divide and Conquer plus leveraging the problem feature of **overlapping subproblems** plus the optimization with **memoization** (top-down) or **tabulation** (bottom-up) methodology.

DP also translates the original problem into a collection of subproblems (tree).
In practice, such process involves laying out the metadata/state for each subproblem, the recurrence relation of the problem and its subproblems (what is/are the action(s) that transit from state 1…i to i+1), and base cases.
What’s special in DP is that, while applying top-down approach with recursion or bottom up approach, it leverages a global **memoization** storing the solution for each metadata (e.g., in the form of 1D array) to prune the original tree and get rid of solving overlapping subproblems.
The most classical example is `509 Fibonacci Number`

, instead of getting an exponential complexity using just Divide and Conquer, with DP leverages the feature of overlapping subproblems and renders an \(O(N)\) time complexity with \(O(N)\) space complexity (or \(O(1)\) with **state compression**).

On the other hand, Backtracking is an *orthoganal* concept, it targets at **constraint satisfaction problem**, i.e., finding all solution(s) that satisfies the target requirements.
The algorithm can be thought of as the process of **traversing a N-ary decision tree**: upon each step, it selects an option and builds a partial candidate to the solutions and abandons a candidate when it is not possible for it to be valid in later steps.
In practice, the solutions involves a global solution(s) container, remaining/full options vector, path vector (the partial solution with the sequence of decisions made before), and termination conditions (optional early termination for invalid ones and final wrap up for valid full solution).
Backtracking does involves recursive calls during the tree traversal, yet its tree representation *has a different semantics: typically there is neither pattern of subproblems nor overlapping ones in DP*.

#### Something Practical

There is an giant array of problems in these three categories, below is a non-exhaustive list from Leetcode with my notes:

*Dynamic Programming*

`509 Fibonacci Number`

A classical example to practice the concepts above.

`322 Coin Change`

\(\approx509\) the recurrence relation is slightly more complex, mincoin(i) is the minimum among 1+mincoin(i-coin), where coin is a element of the given coins set.

`416 Partition Equal Subset Sum`

Variant of the classical 0-1 knapsack problem. The problem is equivalent to determining whether we could find n elements (objects) in the set which sums up to half the original sum (bag weight). Metadata includes N (first N elements) and target sum S. To find the state transition function, think of the action for element i, we have only 2 options, either to pick or not, hence, \(dp(n,s)=dp(n,s-arr[n])\) OR \(dp(n-1, s)\). One could also later optimize the space complexity of the 2D cache array to 1D array.

`518 Coin Change 2`

Variant of unbounded knapsack problem. Unlike 322, this time we want the number of combinations rather than minimum coin number. Same metadata as 416, but \(dp(n,s)=dp(n-1,s)+dp(n,s-arr(n))\);

`1143 Longest Common Subsequence`

DP is a powerful tool to solve String(s) related problems. Metadata: 2D DP table value dp(i,j) is the LCS of 1…i of text1, 1…j of text2. State transition function: consider the conditionals of diff elements text1[i] and text2[j], they can either both be part of LCS, or only one of them, hence, \(dp(i,j)=dp(i-1,j-1)+1\) when equals, and \(dp(i,j)=max(dp(i,j-1), dp(i-1,j))\) otherwise.

`72 Edit Distance`

\(\approx 1143\). Same definition of metadata. State transition function: relavant previous states are dp(i-1,j-1), dp(i,j-1) and dp(i-1,j); the function is expected to be in the form of conditionals where the conditonal will be related to word1[i] and word2[j]; given dp(i,j-1), \(dp(i,j)=dp(i,j-1)+1\) (del); given dp(i-1,j), \(dp(i,j)=dp(i-1,j)+1\) (add), \(dp(i,j)=dp(i-1,j-1)+1\) (mod), \(dp(i,j)=dp(i-1,j-1)\) (nop). Hence, if diff elements equals, \(dp(i,j)=dp(i-1,j-1)\) and \(dp(i,j)=min(dp(i,j-1)+1, dp(i-1,j)+1, dp(i-1,j-1)+1)\) otherwise. Remember to bootstrap the base cases (which will not be calculated in the main loop). One could also change the int value of dp to a struct that records both the ED and the operation type during the transition step.

`583 Delete Operation for Two Strings`

First find LCS as in 1143, then delete the rest for each string.

`712 Minimum ASCII Delete Sum for Two Strings`

Again similar metadata as 1143, but the value of dp table is the minimum ASCII sum. The state transition function is similar but put into account the ASCII sum, i.e., \(dp(i,j) = dp(i-1,j-1)\) when word1[i-1] and word2[j-1] equals, \(dp(i,j) = min(dp(i-1,j)+s1[i-1], dp(i,j-1)+s2[j-1])\) otherwise.

`62 Unique Paths`

The metadata and corresponding table, recurrence relation, base cases are explicit in this problem.

`63 Unique Paths II`

\(>62\) need to put into account the obstable matrix when initializing base cases and the recurrence relation becomes a conditional function on the obstable matrix value

`64 Minimum Path Sum`

\(\approx62\) but difference context

`70 Climbing Stairs`

The solution sequence is in fact Fibonacci sequence.

`746 Min Cost Climbing Stairs`

Note that “reach the top of the floor” is defined as lastindex+1. Otherwise, it is a simple DP problem.

`120 Triangle`

Solution with $O(n^{2})$ space is trivial. The interesting part is the requirement of \(O(n)\) space complexity (state compression). Hence, we use a vector to record the min sum for the current layer. It is easier to go from the bottom (as base cases) to the top. If we go from the top (as base cases) to the bottom, we need to iterate the current layer in the reverse order to avoid overwrites.

`96 Unique Binary Search Trees`

Note that we need a dummy base case dp(0)=1. With the property of binary search tree, for each choice of j, 1…j must be at the left branch while j+1…i at the right. The recurrence relation: \(dp[i]=\sum_{j=0}^{j=i-1}dp[j]\times dp[i-j-1]\).

`279 Perfect Squares`

Note the base case \(dp[0]=0\) besides $dp[1]=1$. Recurrence relation \(dp[i]=\min_{j=1}^{i-j^{2}>=0}dp[i-j^{2}]+1\)

`122 Best Time to Buy and Sell Stock II`

Unlike

`121 Best Time to Buy and Sell Stock`

(one transaction, \(O(n)\) time and \(O(1)\) space to record min price and max profit), inifinite transaction. \(N\times 2\) (\(2\times N\), i.e., larger continuous chunk for inner array is more custom for cache accesses and therefore faster) array metadata: stock num \(\in (0,1)\) at the end of day n. Can also use non-dp algorithm \(\sum_{arr[i]-arr[i-1>0]}arr[i]-arr[i-1]\). Recurrence relation (only 3 actions, buy, sell, static): \(dp[i][0] = max(dp[i-1][0], dp[i-1][1]+prices[i])\), \(dp[i][1] = max(dp[i-1][1], dp[i-1][0]-prices[i])\).

`714 Best Time to Buy and Sell Stock with Transaction Fee`

\(\approx 122\) but with transaction fee. Just add transaction fee delta in recurrence formula: \(dp[i][0] = max(dp[i-1][0], dp[i-1][1]+prices[i]-fee)\). One could then compress state from \(O(N)\) to $O(1)$.

`309 Best Time to Buy and Sell Stock with Cooldown`

Same metadata, yet actions include cooldown. Hence, recurrence relation: \(dp[i][0] = max(dp[i-1][0], dp[i-1][1]+prices[i]); dp[i][1] = max(dp[i-1][1], dp[i-2][0]-prices[i])\).

`188 Best Time to Buy and Sell Stock IV`

\(>122\) with restrictions of K transactions, if $K>2N$, it is reducted to 188, otherwise, metadata \(N\times (K+1) \times 2\) indicating the best profit with k transactions used, (0,1) stock at the end of day n. Recurrence relation: \(dp[i][j][0] = max(dp[i-1][j][0], dp[i-1][j][1]+prices[i]) \quad and \quad dp[i][j][1] = max(dp[i-1][j][1], dp[i-1][j-1][0]-prices[i])\) when \(j-1\geq 0\). Edge cases: use -inf+delta to indicate the impossibility of certain state and prevent overflow. One could further compress the state.

`123 Best Time to Buy and Sell Stock III`

\(<188\), just plug in \(k=2\).

*Backtracking*

`46 Permutations`

A collection of distinct integers. The backtrack function takes the path vector and options vector (the list of given integers) as arguments. Inside the function, first return if invalid or full solution hits, then iterate the options vector, push new choice in path, backtrack, and pop before new iteration (think of the decision tree, each iteration is of the same height, so a recovery of the path (and available options vector) is needed after the recursive call).

`47 Permutations II`

Unlike 46, the collection might contain duplicates yet we want all possible unique permutations. We use global solution set to avoid solution duplicates (convert it back to vector at the end); also besides path argument and remaining options argument, an int argument indicating the target size of a candidate is needed for the terminal condition since the remaining options set could change. There are also other options for backtrack arguments, e.g., use full options vector instead, then we need an extra vector argument to record the chosen indices (which is unique, due to duplicate elements) of the full options vector and check if the new option is made before after each decision.

`77 Combinations`

This question asks for combination rather than permutation, hence, after each decision of the element of index i, we need to update the remaining options list to include only i+1… to avoid duplicate combinations.

`39 Combination Sum`

\(\approx77\) This time when updating the remaining options list, we include i, i+1… since each element could be used multiple times. Another change is that the terminal condition is to check the sum of path elements and the target.

`40 Combination Sum II`

\(\approx39\) but the given collection now have duplicate numbers at arbitrary indices. The key is how to avoid duplicate combinations. To do that, first sort the collection before starting the backtracking. Meanwhile, in the main loop of backtracking, besides updating available choices as i+1…, we need to skip the repeated elements since their branches are overlapping with the first of these repeated elements (just increment until collection[i]!=collection[i+1])

`216 Combination Sum III`

\(\approx39,40\) but requires exact number of decisions in tha path, just change the terminal condition correspondinly.

`78 Subsets`

\(\approx77\) besides updating remain options list to i+1… to avoid duplication, the solution set needs to include candidates that “were partial”.

`90 Subsets II`

\(\approx77\) but there are duplicates in the given collection. Need to sort and skip duplicate elements in the backtracking loop as in 40.

`51 N-Queens`

The global solution container is a vector of string vectors (each string vector is a ASCII chessboard display). The context specific constraint is to check all columns and left/right diagonals.

`52 N-Queens II`

\(<51\), only need to maintain a counter rather than a vector of string vectors.

`17 Letter Combinations of a Phone Number`

Extensive use of substr (slice) and += (append) string API.

*Divide and Conquer*

`169 Majority Element`

If we divide array A by half, then the majority element of A must be the majority element of A1 or/and A2. We could then conquer and combine the result for subproblems A1 and A2. Recurrence relation \(T(n)=2T(\frac{N}{2})+2n\), by master theorem, \(T(n)=\Theta(n\log n)\). Note that for the class of problems to find the majority element, Boyer-Moore Voting Algorithm gives \(\mathcal{O}(N)\) time and \(\mathcal{O}(1)\) space complexity. A single pass of increment/replace/decrement (at the end of which the majority element will be the candidate) is enough since the majority element is assumed to be present.

`229 Majority Element II`

\(\approx 169\) but divide array A by three pieces. For \(\mathcal{O}(N)\) time and \(\mathcal{O}(1)\) space complexity, use Boyer-Moore Voting Algorithm with 2 candidate/counter pairs during the first pass and a second pass to verity the candidates.

`23 Merge k Sorted Lists`

Divide k sorted lists into 2 k/2 sorted lists recursively until k=0,1,or 2. Solve the base cases of k=2 and combine the result of 2 subproblems leveraging the basic helper API

`21 Merge Two Sorted Lists`

.