Dynamic programming is a technique for solving problems by breaking them down into smaller subproblems and solving them recursively. Both top-down and bottom-up dynamic programming use this approach, but they differ in the order in which the subproblems are solved.
Top-Down Dynamic Programming:
Top-down dynamic programming (also known as memoization) begins by breaking down the original problem into smaller subproblems, similar to bottom-up dynamic programming, but it solves each subproblem recursively, from the top of the problem tree to the bottom, before moving on to the next subproblem. In this approach, we store the solutions to subproblems in a lookup table (also called memoization table) so that we don’t have to re-compute them every time they are needed. This helps to avoid redundant computations and reduce the time complexity of the algorithm.
A classic example of a problem that can be solved using top-down dynamic programming is the Fibonacci sequence. Here’s what the top-down implementation in Java would look like:
public int fibonacci(int n, int[] memo) {
if (n <= 1) {
return n;
}
if (memo[n] != 0) {
return memo[n];
}
memo[n] = fibonacci(n-1, memo) + fibonacci(n-2, memo);
return memo[n];
}Bottom-Up Dynamic Programming:
Bottom-up dynamic programming, on the other hand, begins by breaking down the original problem into smaller subproblems and solves them iteratively, from the smallest subproblem to the largest, gradually building up to the solution of the original problem. In this approach, we typically use an array to store the solutions to subproblems, with each element representing the solution to a specific subproblem. This can be more efficient than the top-down approach in terms of both time and memory complexity.
Let’s modify our Fibonacci example to use the bottom-up approach in Java:
public int fibonacci(int n) {
if (n <= 1) {
return n;
}
int[] memo = new int[n+1];
memo[0] = 0;
memo[1] = 1;
for (int i = 2; i <= n; i++) {
memo[i] = memo[i-1] + memo[i-2];
}
return memo[n];
}In summary, while both top-down and bottom-up dynamic programming use the same approach of breaking down problems into smaller subproblems, they differ in the order in which the subproblems are solved. Top-down solves subproblems recursively from top to bottom, while bottom-up solves subproblems iteratively from bottom to top. The choice between them depends on the specific problem at hand and the efficiencies required.