Divide and conquer algorithms and dynamic programming both employ similar techniques to solve complex problems, but they differ in how they combine the smaller subproblems.
Divide and conquer algorithm divides the larger problem into smaller subproblems, solves each subproblem independently and then combines the subproblems’ solutions to solve the original problem. On the other hand, Dynamic programming divides the problem into overlapping subproblems and then solves each subproblem only once and stores the result for future use.
In contrast to divide and conquer algorithms, dynamic programming often use memoization (top-down) or building a table (bottom-up) to store the solutions of subproblems. This approach optimizes the complexity of the algorithm by eliminating the need to solve the same subproblems multiple times.
For example, let’s consider the problem of finding the n-th Fibonacci number.
A divide and conquer algorithm for the Fibonacci problem could look like:
public static int fibonacci(int n) {
if (n == 0) return 0;
if (n == 1) return 1;
return fibonacci(n - 1) + fibonacci(n - 2);
}This algorithm recursively computes the n-th Fibonacci number by dividing the problem into two subproblems (n-1) and (n-2). However, as we can see, this algorithm will perform multiple calculations of the same subproblem which can be optimized with dynamic programming.
A dynamic programming approach to solving Fibonacci problem would look something like this:
public static int fibonacciDP(int n) {
int[] memo = new int[n + 1];
return fibonacciMemo(n, memo);
}
private static int fibonacciMemo(int n, int[] memo) {
if (n == 0) return 0;
if (n == 1) return 1;
if (memo[n] != 0) {
return memo[n];
}
memo[n] = fibonacciMemo(n - 1, memo) + fibonacciMemo(n - 2, memo);
return memo[n];
}This algorithm uses dynamic programming to optimize the time complexity of the algorithm. It avoids repeated computation of the same subproblem in the divide and conquer approach by storing the results in memoization table. This way, the algorithm can compute the n-th Fibonacci number in O(n) time complexity rather than exponential time complexity O(2n) of the normal divide and conquer approach.
Therefore, while divide and conquer and dynamic programming approaches share similarities in that they both rely on solving smaller subproblems, dynamic programming tends to use memoization techniques or building tables to optimize subproblem solution storage and reuse.