How do you determine if a problem can be solved using dynamic programming?

To determine if a problem can be solved using dynamic programming, we usually look for two main properties:

1. **Optimal Substructure** - if a problem can be broken down into smaller subproblems and the optimal solution for the original problem can be constructed efficiently from the optimal solutions of its subproblems, then the problem exhibits optimal substructure. In other words, the problem can be solved using a recursive approach where the solution to the original problem depends on the solutions to its subproblems. This is a key property for dynamic programming and it allows us to apply memoization or tabulation to avoid redundant computations.

2. **Overlapping Subproblems** - if the subproblems required to solve the original problem recur repeatedly, then the problem exhibits overlapping subproblems. In other words, the same subproblems are being solved multiple times during the computation of the solution. This can result in redundant computations that can be avoided using dynamic programming.

Once we have established that a problem exhibits these two properties, we can consider solving it using dynamic programming by either using the top-down approach (memoization) or the bottom-up approach (tabulation).

For example, let’s consider the problem of finding the n-th Fibonacci number given n. This problem exhibits both optimal substructure and overlapping subproblems. The n-th Fibonacci number can be computed recursively as the sum of the (n-1)th and (n-2)th Fibonacci numbers. In other words, the solution to the original problem depends on the solutions to its subproblems. Additionally, the computation of the (n-1)th and (n-2)th Fibonacci numbers are subproblems that are repeated multiple times during the computation of the solution for the original problem.

Here is an example code for computing the n-th Fibonacci number using dynamic programming (bottom-up approach or tabulation) in Java:

public static int fibonacci(int n) {
    if(n == 0) {
        return 0;
    }
    if(n == 1 || n == 2) {
        return 1;
    }
    int[] fib = new int[n+1];
    fib[1] = 1;
    fib[2] = 1;
    for(int i=3; i<=n; i++) {
        fib[i] = fib[i-1] + fib[i-2];
    }
    return fib[n];
}

In this code, we are storing the solutions to the subproblems (i.e., the ith Fibonacci number) in an array called fib. We start by initializing fib[1] and fib[2] to 1 (since they are base cases). We then use a loop to compute fib[i] as the sum of fib[i-1] and fib[i-2]. Finally, we return fib[n], which is the solution to the original problem. This code runs in O(n) time and O(n) space, which is much faster than the naive recursive approach that runs in O(2ⁿ) time.