Getting started with Dynamic Programming

In this article, we will cover the core concepts of dynamic programming(DP) and discuss all the fundamentals required to get started with it. This article aims to provide a base for DP so that it would be easier to take the algorithmic approach to solve any DP problem.

What is Dynamic Programming

Dynamic programming involves finding an optimal solution to a given problem that contains overlapping subproblems and uses the technique of memoization for the subproblems to find an optimal solution.

Overlapping subproblems involves recursion. In recursion, we break a bigger problem into similar subproblems and these subproblems are solved first and the result of these subproblems is combined to get the result of the bigger problem. With recursion, we solve each and every subproblem irrespective of any other similar subproblem which we might have already solved in the recursion tree. Let us understand this with an example.

Below is the recursive approach to find the nth Fibonacci number of any given number.

public static int findFib(int num){
        if(num <= 1){
            return num;
        }
        return findFib(num - 1) + findFib(num -2);
    }

    public static void main(String[] args) {
        int fib = Fibonacci.findFib(5);
        System.out.println(fib);
    }

For this recursive approach, if we see the recursion tree there are many overlapping subproblems.

For the input number 5 the same findFib() function is getting called repeatedly for the same value for multiple times. For example, findFib(2) is called thrice and this is an overlapping subproblems and it makes the time-complexity to be exponential as O(2^n).

This time complexity can be reduced and optimized with DP and the way in which it can be optimized is by using memoization.

What is Memoization

Memoization is a technique to maintain a table of subproblems that are already solved. With memoization, the exponential time complexity can be reduced to polynomial complexity(O(n^2)) or even to linear(O(n)) such as in Kadane's algorithm.

For example, in the above Fibonacci problem we can maintain a table of subproblems and perform a lookup in the table if that subproblem is already solved and then instead of going into recursion for that subproblem we can directly return the value from the table and hence the recursive call can be preserved.

Hence, with dynamic programming we can avoid the recalculation of the subproblems and can reuse the precalculated subproblems solution. We can store these subproblem solutions either in a table or array.

For the above problem let us apply DP and use an array for memoization.

static int[] fib = new int[6];
    public static int findFibDPBottomUp(int num){
        if(num <= 1){
            return num;
        }
        if (fib[num] != 0){
            return fib[num];
        }
        fib[num] = findFib(num - 1) + findFib(num -2);
        return fib[num];
    }

    public static void main(String[] args) {
        Arrays.fill(fib, 0);
        System.out.println(Fibonacci.findFibDPBottomUp(5));
    }

The above approach is called top-down approach but it can be solved using bottom-up approach too. But remember, all problems can't be solved using both the approach.

Now, let us discuss about this 2 approach.

Bottom-Up Approach

In the bottom-up approach, we start solving the problem starting from the valid smallest subproblem and then we step up till we solve the complete problem. While solving the sub-problems, we store all the computed values in a table. As larger problems are solved, pre-computed values for the smaller problem can be re-used.

Now, let us see the code how the above Fibonacci problem can be solved with Bottom-up dynamic programming approach.

static int[] fib = new int[10];
public static int findFibDPBottomUp(int num){
        if(num <= 1){
            return num;
        }
        fib[0] = 1;
        fib[1] = 1;
        for (int i = 2; i < num; i++){
            fib[i] = fib[i - 1] + fib[i - 2];
        }
        return fib[num - 1];
    }


    public static void main(String[] args) {
        Arrays.fill(fib, 0);
        System.out.println(Fibonacci.findFibDPBottomUp(9));
    }

Top-Down Approach

In this approach, the problem is broken into subproblems and each of these subproblems is solved and the solutions to these subproblems are stored in an array so that these pre-computed solutions of the subproblems can be reused rather than recomputing it.

Below is the top-down approach for the Fibonacci problem.

static int[] fib = new int[10];
    public static int findFibDPTopDown(int num){
        if(num <= 1){
            return num;
        }
        if (fib[num] != 0){
            return fib[num];
        }
        fib[num] = findFib(num - 1) + findFib(num -2);
        return fib[num];
    }

Dynamic Programming Examples

There are many problems which can be optimised through dynamic programming. Below are some of the examples:

• Matrix Chain Multiplication
• Subset Sum
• 0/1 Knapsack
• String algos such as Longest Common SubSequence(LCS)
• Graph algorithms such as Bellman-Ford algorithm, Shortest Path Algorithm, etc.

Conclusion

In this article, we discussed the core concepts of dynamic programming(DP) and discussed all the fundamentals required to get started with it.