Dynamic Programming Revisited

Today in the Twin Cities of Minneapolis and St. Paul we had snow on and off for several hours. It does not seem we have any accumulation on the road surface. This might change tomorrow. Snow is expected for most of the day. It seems winter has arrived.

A friend mentioned the article “Tokyo citizens may have developed COVID-19 herd immunity, say researchers” by Sally Robertson. If interested, read the article and then continue reading this post…

…The paper describes interesting hypothesis of what may have happened during the months of summer 2020 in Tokyo, Japan. The key observations are the large population, the use of masks which has been common among the population for decades in order to protect each other from the common flu, the use of public transportation, and reduce geographical size on the metropolitan city of Tokyo.

Hopefully the article has brought an additional perspective on how to deal with the COVID-19 pandemic.

Let’s get to the main subject of this post. Dynamic Programming has been around for about 70 years. The idea is to simplify a complicated problem by solving sub problems, saving the results, and then combining them into a solution. Please note that if there is no solution for a problem, dynamic programming will not provide one.

I believe some years ago I generated a post on Dynamic Programming. I have to apologize for the formatting of the code sections in it. I no longer use that plugin. If I have some time I will see if I can update it. In addition, the code for that post is not in GitHub.

A typical problem that is used to show Dynamic Programming is to develop a function / method that generate the Fibonacci number for a specified integer. The idea for the series is quite simple. Start with two integers 0 and 1. If you ask for the Fibonacci number of 0 the result is 0. For 1 the result is 1. From then on the result for 2 is 1. The reason is that we need to add the two previous Fibonacci numbers, which in this case are 0 + 1 = 1. The next Fibonacci number for 3 is 2 which we can generate by adding the two previous values 1 + 1 = 2. For a list of the first few Fibonacci numbers you can look here.

Let’s build a test scaffolding and experiment with different approaches. We will use the Java programming language, the VSCode IDE and a Windows 10 platform. As usual, results should be the same within the data types and nuances of the computer programming language you choose.

50
main <<< n: 50
main <<< count: 1 fibRecursive(0): 0 (0 ms)
main <<< count: 1 fibRecursive(1): 1 (0 ms)
main <<< count: 1 fibRecursive(2): 1 (0 ms)
main <<< count: 3 fibRecursive(3): 2 (0 ms)
main <<< count: 5 fibRecursive(4): 3 (0 ms)
main <<< count: 9 fibRecursive(5): 5 (0 ms)
main <<< count: 15 fibRecursive(6): 8 (0 ms)
main <<< count: 25 fibRecursive(7): 13 (0 ms)
main <<< count: 41 fibRecursive(8): 21 (0 ms)
main <<< count: 67 fibRecursive(9): 34 (0 ms)
main <<< count: 109 fibRecursive(10): 55 (0 ms)
main <<< count: 177 fibRecursive(11): 89 (0 ms)
main <<< count: 287 fibRecursive(12): 144 (0 ms)
main <<< count: 465 fibRecursive(13): 233 (0 ms)
main <<< count: 753 fibRecursive(14): 377 (0 ms)
main <<< count: 1219 fibRecursive(15): 610 (0 ms)
main <<< count: 1973 fibRecursive(16): 987 (0 ms)
main <<< count: 3193 fibRecursive(17): 1597 (0 ms)
main <<< count: 5167 fibRecursive(18): 2584 (0 ms)
main <<< count: 8361 fibRecursive(19): 4181 (0 ms)
main <<< count: 13529 fibRecursive(20): 6765 (0 ms)
main <<< count: 21891 fibRecursive(21): 10946 (0 ms)
main <<< count: 35421 fibRecursive(22): 17711 (0 ms)
main <<< count: 57313 fibRecursive(23): 28657 (0 ms)
main <<< count: 92735 fibRecursive(24): 46368 (0 ms)
main <<< count: 150049 fibRecursive(25): 75025 (0 ms)
main <<< count: 242785 fibRecursive(26): 121393 (0 ms)
main <<< count: 392835 fibRecursive(27): 196418 (1 ms)
main <<< count: 635621 fibRecursive(28): 317811 (1 ms)
main <<< count: 1028457 fibRecursive(29): 514229 (1 ms)
main <<< count: 1664079 fibRecursive(30): 832040 (2 ms)
main <<< count: 2692537 fibRecursive(31): 1346269 (3 ms)
main <<< count: 4356617 fibRecursive(32): 2178309 (6 ms)
main <<< count: 7049155 fibRecursive(33): 3524578 (9 ms)
main <<< count: 11405773 fibRecursive(34): 5702887 (14 ms)
main <<< count: 18454929 fibRecursive(35): 9227465 (23 ms)
main <<< count: 29860703 fibRecursive(36): 14930352 (37 ms)
main <<< count: 48315633 fibRecursive(37): 24157817 (59 ms)
main <<< count: 78176337 fibRecursive(38): 39088169 (97 ms)
main <<< count: 126491971 fibRecursive(39): 63245986 (157 ms)
main <<< count: 204668309 fibRecursive(40): 102334155 (253 ms)
main <<< count: 331160281 fibRecursive(41): 165580141 (411 ms)
main <<< count: 535828591 fibRecursive(42): 267914296 (670 ms)
main <<< count: 866988873 fibRecursive(43): 433494437 (1086 ms)
main <<< count: 1402817465 fibRecursive(44): 701408733 (1764 ms)
main <<< count: 2269806339 fibRecursive(45): 1134903170 (2853 ms)
main <<< count: 3672623805 fibRecursive(46): 1836311903 (4597 ms)
main <<< count: 5942430145 fibRecursive(47): 2971215073 (7411 ms)
main <<< count: 9615053951 fibRecursive(48): 4807526976 (11986 ms)
main <<< count: 15557484097 fibRecursive(49): 7778742049 (19269 ms)
main <<< count: 25172538049 fibRecursive(50): 12586269025 (31222 ms)

main <<< count: 1 fibMemo(0): 0 (2600 ns)
main <<< count: 1 fibMemo(1): 1 (500 ns)
main <<< count: 1 fibMemo(2): 1 (700 ns)
main <<< count: 3 fibMemo(3): 2 (1600 ns)
main <<< count: 5 fibMemo(4): 3 (1600 ns)
main <<< count: 7 fibMemo(5): 5 (1300 ns)
main <<< count: 9 fibMemo(6): 8 (2200 ns)
main <<< count: 11 fibMemo(7): 13 (1600 ns)
main <<< count: 13 fibMemo(8): 21 (1500 ns)
main <<< count: 15 fibMemo(9): 34 (1600 ns)
main <<< count: 17 fibMemo(10): 55 (1700 ns)
main <<< count: 19 fibMemo(11): 89 (1900 ns)
main <<< count: 21 fibMemo(12): 144 (1800 ns)
main <<< count: 23 fibMemo(13): 233 (3500 ns)
main <<< count: 25 fibMemo(14): 377 (2100 ns)
main <<< count: 27 fibMemo(15): 610 (2200 ns)
main <<< count: 29 fibMemo(16): 987 (2300 ns)
main <<< count: 31 fibMemo(17): 1597 (7400 ns)
main <<< count: 33 fibMemo(18): 2584 (5800 ns)
main <<< count: 35 fibMemo(19): 4181 (500 ns)
main <<< count: 37 fibMemo(20): 6765 (500 ns)
main <<< count: 39 fibMemo(21): 10946 (500 ns)
main <<< count: 41 fibMemo(22): 17711 (500 ns)
main <<< count: 43 fibMemo(23): 28657 (500 ns)
main <<< count: 45 fibMemo(24): 46368 (500 ns)
main <<< count: 47 fibMemo(25): 75025 (600 ns)
main <<< count: 49 fibMemo(26): 121393 (500 ns)
main <<< count: 51 fibMemo(27): 196418 (600 ns)
main <<< count: 53 fibMemo(28): 317811 (700 ns)
main <<< count: 55 fibMemo(29): 514229 (700 ns)
main <<< count: 57 fibMemo(30): 832040 (600 ns)
main <<< count: 59 fibMemo(31): 1346269 (700 ns)
main <<< count: 61 fibMemo(32): 2178309 (700 ns)
main <<< count: 63 fibMemo(33): 3524578 (700 ns)
main <<< count: 65 fibMemo(34): 5702887 (800 ns)
main <<< count: 67 fibMemo(35): 9227465 (800 ns)
main <<< count: 69 fibMemo(36): 14930352 (700 ns)
main <<< count: 71 fibMemo(37): 24157817 (2500 ns)
main <<< count: 73 fibMemo(38): 39088169 (700 ns)
main <<< count: 75 fibMemo(39): 63245986 (800 ns)
main <<< count: 77 fibMemo(40): 102334155 (800 ns)
main <<< count: 79 fibMemo(41): 165580141 (800 ns)
main <<< count: 81 fibMemo(42): 267914296 (800 ns)
main <<< count: 83 fibMemo(43): 433494437 (800 ns)
main <<< count: 85 fibMemo(44): 701408733 (800 ns)
main <<< count: 87 fibMemo(45): 1134903170 (800 ns)
main <<< count: 89 fibMemo(46): 1836311903 (900 ns)
main <<< count: 91 fibMemo(47): 2971215073 (900 ns)
main <<< count: 93 fibMemo(48): 4807526976 (900 ns)
main <<< count: 95 fibMemo(49): 7778742049 (2600 ns)
main <<< count: 97 fibMemo(50): 12586269025 (900 ns)

main <<< count: 1 fibBottomUp(0): 0 (4200 ns)
main <<< count: 1 fibBottomUp(1): 1 (400 ns)
main <<< count: 1 fibBottomUp(2): 1 (500 ns)
main <<< count: 1 fibBottomUp(3): 2 (1700 ns)
main <<< count: 1 fibBottomUp(4): 3 (1600 ns)
main <<< count: 1 fibBottomUp(5): 5 (1600 ns)
main <<< count: 1 fibBottomUp(6): 8 (3000 ns)
main <<< count: 1 fibBottomUp(7): 13 (1600 ns)
main <<< count: 1 fibBottomUp(8): 21 (1600 ns)
main <<< count: 1 fibBottomUp(9): 34 (1700 ns)
main <<< count: 1 fibBottomUp(10): 55 (1700 ns)
main <<< count: 1 fibBottomUp(11): 89 (1700 ns)
main <<< count: 1 fibBottomUp(12): 144 (1700 ns)
main <<< count: 1 fibBottomUp(13): 233 (3100 ns)
main <<< count: 1 fibBottomUp(14): 377 (1700 ns)
main <<< count: 1 fibBottomUp(15): 610 (2700 ns)
main <<< count: 1 fibBottomUp(16): 987 (5200 ns)
main <<< count: 1 fibBottomUp(17): 1597 (2000 ns)
main <<< count: 1 fibBottomUp(18): 2584 (2000 ns)
main <<< count: 1 fibBottomUp(19): 4181 (4200 ns)
main <<< count: 1 fibBottomUp(20): 6765 (2000 ns)
main <<< count: 1 fibBottomUp(21): 10946 (1900 ns)
main <<< count: 1 fibBottomUp(22): 17711 (2100 ns)
main <<< count: 1 fibBottomUp(23): 28657 (1900 ns)
main <<< count: 1 fibBottomUp(24): 46368 (1800 ns)
main <<< count: 1 fibBottomUp(25): 75025 (1900 ns)
main <<< count: 1 fibBottomUp(26): 121393 (1900 ns)
main <<< count: 1 fibBottomUp(27): 196418 (1900 ns)
main <<< count: 1 fibBottomUp(28): 317811 (1900 ns)
main <<< count: 1 fibBottomUp(29): 514229 (1900 ns)
main <<< count: 1 fibBottomUp(30): 832040 (2000 ns)
main <<< count: 1 fibBottomUp(31): 1346269 (2000 ns)
main <<< count: 1 fibBottomUp(32): 2178309 (2000 ns)
main <<< count: 1 fibBottomUp(33): 3524578 (3900 ns)
main <<< count: 1 fibBottomUp(34): 5702887 (2300 ns)
main <<< count: 1 fibBottomUp(35): 9227465 (2200 ns)
main <<< count: 1 fibBottomUp(36): 14930352 (2100 ns)
main <<< count: 1 fibBottomUp(37): 24157817 (2200 ns)
main <<< count: 1 fibBottomUp(38): 39088169 (2200 ns)
main <<< count: 1 fibBottomUp(39): 63245986 (4300 ns)
main <<< count: 1 fibBottomUp(40): 102334155 (2200 ns)
main <<< count: 1 fibBottomUp(41): 165580141 (2200 ns)
main <<< count: 1 fibBottomUp(42): 267914296 (2500 ns)
main <<< count: 1 fibBottomUp(43): 433494437 (2300 ns)
main <<< count: 1 fibBottomUp(44): 701408733 (2300 ns)
main <<< count: 1 fibBottomUp(45): 1134903170 (4200 ns)
main <<< count: 1 fibBottomUp(46): 1836311903 (4400 ns)
main <<< count: 1 fibBottomUp(47): 2971215073 (2400 ns)
main <<< count: 1 fibBottomUp(48): 4807526976 (2400 ns)
main <<< count: 1 fibBottomUp(49): 7778742049 (2400 ns)
main <<< count: 1 fibBottomUp(50): 12586269025 (2400 ns)

We have a long screen capture which can be divided into four parts. The first part is to parse a number (in this case 50) and call three different implementations that should generate the Fibonacci number for monotonically ascending numbers from 0 to n.

We display a count which we will discuss shortly, the argument used in a call that seems to return the associated Fibonacci number, and an execution time. The first group expresses the time in milliseconds, and the other two in nanoseconds. The numbers generated for the same integer seems to return the same results using the three different functions. In addition they also seem to match the results from the web page.

    // **** constant(s) ****
    static final long MAX_FIB = 92;

    // **** global variable(s) ****
    static long count = 0;

The code shows a constant and a variable count that is used to count the number of times a function is called when generating a Fibonacci number for a specified integer. That is the value we saw in the output. You should have noticed that the counts are considerably smaller in the last two implementations. The same holds true for the execution times of the different functions.

    /**
     * Test scaffolding
     */
    public static void main(String[] args) {
        
        // **** open scanner ****
        Scanner sc = new Scanner(System.in);

        // **** read which fibonnaci number to compute ****
        long n = Long.parseLong(sc.nextLine().trim());

        // **** close scanner ****
        sc.close();

        // **** check entered value ****
        if (n >= 0 && n <= MAX_FIB)
            System.out.println("main <<< n: " + n);
        else {
            System.out.println("main <<< invalid n: " + n);
            System.exit(-1);
        }

        // **** loop generating a set of Fibonacci numbers ****
        for (int i = 0; i <= n; i++) {

            // **** clear counter ****
            count = 0;

            // **** get start time ****
            long startTime = System.currentTimeMillis();

            // **** generate fibonacci number ****
            long fibNumber = fibRecursive(i);

            // **** get end time ****
            long endTime = System.currentTimeMillis();

            // **** display result ****
            System.out.println("main <<< count: " + count + " fibRecursive(" + i + "): " + fibNumber + " (" + (endTime - startTime) + " ms)");
        }
        System.out.println();

        // **** ****
        long[] memo = new long[(int)MAX_FIB + 1];

        // **** loop generating a set of Fibonacci numbers ****
        for (int i = 0; i <= n; i++) {

            // **** clear counter ****
            count = 0;
                        
            // **** initialize memo ****
            Arrays.fill(memo, 0);

            // **** get start time ****
            long startTime = System.nanoTime();

            // **** generate fibonacci number ****
            long fibNumber = fibMemo(i, memo);

            // **** get end time ****
            long endTime = System.nanoTime();

            // **** display result ****
            System.out.println("main <<< count: " + count + " fibMemo(" + i + "): " + fibNumber + " (" + (endTime - startTime) + " ns)");
        }
        System.out.println();

        // **** loop generating a set of Fibonacci numbers ****
        for (int i = 0; i <= n; i++) {

            // **** clear counter ****
            count = 0;

            // **** get start time ****
            long startTime = System.nanoTime();

            // **** generate fibonacci number ****
            long fibNumber = fibBottomUp(i);

            // **** get end time ****
            long endTime = System.nanoTime();

            // **** display result ****
            System.out.println("main <<< count: " + count + " fibBottomUp(" + i + "): " + fibNumber + " (" + (endTime - startTime) + " ns)");
        }
    
    }

As expected, we use a scanner to read the number of integers that we will use to generate the associated Fibonacci numbers. We the close the scanner because it is no longer needed.

We check the specified number to make sure n is in the range [0:MAX_FIB]. The reason being is that Fibonacci numbers are specified from 0 (there are no Fibonacci numbers associated with negative integers). So why do we specify a top limit? The reason is that we are using long integers and we will encounter overflows past 92. If you wish, you can edit the limit, set it to 100, and give it a try. We could have implemented the functions using a different data type (i.e., BigInteger) and if my memory does not fail, I have done so in some post.

We have three similar loops. Each lop clears the counter on each pass. The first loop uses a recursive approach. The second loop uses memoization. Memoization is the name of a technique that stores intermediate values of operations expecting that the results will be used multiple times when generating the global result.

A simple example of memoization would be if you are asked to display the sum of a set of 1s. You could use an array and store the results as you go. For example if the sum of 5 is needed, you could calculate sum = 1 + 1 + 1 + 1 + 1 = 5 or just provide 4 + 1. Of course in this example we could just return the number n and avoid an array with each value.

    /**
     * Compute the specified Fibonacci number.
     * Recursive method.
     * Execution time: O(2 ^ n)
     */
    static long fibRecursive(long n) {

        // **** count this call ****
        count++;

        // **** end condition ****
        if (n <= 0)
            return 0;

        if (n == 1 || n == 2)
            return 1;

        // **** recursion ****
        long fib = fibRecursive(n - 2) + fibRecursive(n - 1);

        // **** return fibonacci number ****
        return fib;
    }

This is a text book implementation of a recursive function. We have an end condition. Each time we need to calculate the next Fibonacci number we just call the same function with n – 2 and n – 1 arguments. When done we return the expected value. This is quite simple and elegant. Go back to the screen capture and look at the counts and execution times. As I am typing this post, I think that we could have implemented a fourth approach just using loops. Chances are the times would have reduced considerably and the stack would just hold a single call.

    /**
     * Compute the specified Fibonacci number.
     * Using memoization.
     * Recursive call.
     * Execution time:  O(2 * n + 1) = O(n)
     */
    static long fibMemo(long n, long[] memo) {

        // **** count this call ****
        count++;

         // **** end condition ****
        if (n == 0)
            return 0;

        // **** first two values ****
        if (n == 1 || n == 2)
            return 1;

        // **** check for value ****
        if (memo[(int)n] != 0)
            return memo[(int)n];

        // **** recursive ****
        long fib = fibMemo(n - 1, memo) + fibMemo(n - 2, memo);

        // **** store in memo ****
        memo[(int)n] = fib;

        // **** return fibonacci number ****
        return fib;
    }

This function is quite similar to the previous one. The bit difference is the array we use for memoization. Before we perform the recursive call, we check in the memo array to see if we have already computed an intermediate value. If so we just return it. If not available, we make two recursive calls as we did before. Since we use the memo array, they should find previously computed values. Note that after the recursion call we store the new result in the memo array so it can be used in future calls. Now we just return the result.

Go back to the screen capture and verify that the number of calls to this function is considerably less that in the first loop. The times have also decremented significantly so they are now measured in nanoseconds instead of millisecond (1 ms == 1000 ns).

    /**
     * Compute the specified Fibonacci number.
     * Dynamci programming.
     * Bottom up approach.
     * Execution time: O(n)
     */
    static long fibBottomUp(long n) {

        // **** count this call ****
        count++;

        // **** end condition ****
        if (n == 0)
            return 0;

        if (n == 1 || n == 2)
            return 1;
    
        // **** initialization ****
        long[] arr = new long[(int)n + 1];
        arr[1] = arr[2] = 1;

        // **** fill intermediate values ****
        for (int i = 2; i <= n; i++) {
            arr[i] = arr[i - 2] + arr[i - 1];
        }

        // **** return fibonacci number ****
        return arr[(int)n];
    }

This represents a bottom up design approach. We do not use recursion. We use a local array for memoization. The array holds the values as we compute them from 2 (0 and 1 are set) to n. This function represents what Dynamic Programming is all about. Of course some problems are not as simple as this one. We will address a more complex problem in the next post.

Hope you enjoyed solving this problem as much as I did. The entire code for this project can be found in my GitHub repository.

If you have comments or questions regarding this, or any other post in this blog, or if you would like for me to help out with any phase in the SDLC (Software Development Life Cycle) of a project associated with a product or service, please do not hesitate and leave me a note below. If you prefer, send me a private e-mail message. I will reply as soon as possible.

Keep on reading and experimenting. It is the best way to learn, become proficient, refresh your knowledge and enhance your developer toolset!

One last thing, many thanks to all 3220 subscribers to this blog!!!

Keep safe during the COVID-19 pandemic and help restart the world economy.

John

E-mail:  john.canessa@gmail.com

Leave a Reply

Your email address will not be published. Required fields are marked *

This site uses Akismet to reduce spam. Learn how your comment data is processed.