Java Programming – Overlapping Subproblems Property

Dynamic Programming is an algorithmic paradigm that solves a given complex problem by breaking it into subproblems and stores the results of subproblems to avoid computing the same results again.Following are the two main properties of a problem that suggest that the given problem can be solved using Dynamic programming.

In this post, we will discuss first property (Overlapping Subproblems) in detail. The second property of Dynamic programming

• Overlapping Subproblems
• Optimal Substructure
• Overlapping Subproblems:
  Like Divide and Conquer, Dynamic Programming combines solutions to sub-problems. Dynamic Programming is mainly used when solutions of same subproblems are needed again and again. In dynamic programming, computed solutions to subproblems are stored in a table so that these don’t have to recomputed. So Dynamic Programming is not useful when there are no common (overlapping) subproblems because there is no point storing the solutions if they are not needed again. For example, Binary Search doesn’t have common subproblems. If we take example of following recursive program for Fibonacci Numbers, there are many subproblems which are solved again and again.

[pastacode lang=”c” manual=”%2F*%20simple%20recursive%20program%20for%20Fibonacci%20numbers%20*%2F%0Aint%20fib(int%20n)%0A%7B%0A%20%20%20if%20(%20n%20%3C%3D%201%20)%0A%20%20%20%20%20%20return%20n%3B%0A%20%20%20return%20fib(n-1)%20%2B%20fib(n-2)%3B%0A%7D” message=”c” highlight=”” provider=”manual”/]

Recursion tree for execution of fib(5)

                              
                         fib(5)
                     /             \
               fib(4)                fib(3)
             /      \                /     \
         fib(3)      fib(2)         fib(2)    fib(1)
        /     \        /    \       /    \
  fib(2)   fib(1)  fib(1) fib(0) fib(1) fib(0)
  /    \
fib(1) fib(0)

[ad type=”banner”]

We can see that the function f(3) is being called 2 times. If we would have stored the value of f(3), then instead of computing it again, we could have reused the old stored value. There are following two different ways to store the values so that these values can be reused:

• Memoization (Top Down)
• Tabulation (Bottom Up)
• Memoization (Top Down): The memoized program for a problem is similar to the recursive version with a small modification that it looks into a lookup table before computing solutions. We initialize a lookup array with all initial values as NIL. Whenever we need solution to a subproblem, we first look into the lookup table. If the precomputed value is there then we return that value, otherwise we calculate the value and put the result in lookup table so that it can be reused later.

Following is the memoized version for nth Fibonacci Number.

Java

[pastacode lang=”java” manual=”%2F*%20Java%20program%20for%20Memoized%20version%20*%2F%0Apublic%20class%20Fibonacci%0A%7B%0A%20%20final%20int%20MAX%20%3D%20100%3B%0A%20%20final%20int%20NIL%20%3D%20-1%3B%0A%20%0A%20%20int%20lookup%5B%5D%20%3D%20new%20int%5BMAX%5D%3B%0A%20%0A%20%20%2F*%20Function%20to%20initialize%20NIL%20values%20in%20lookup%20table%20*%2F%0A%20%20void%20_initialize()%0A%20%20%7B%0A%20%20%20%20for%20(int%20i%20%3D%200%3B%20i%20%3C%20MAX%3B%20i%2B%2B)%0A%20%20%20%20%20%20%20%20lookup%5Bi%5D%20%3D%20NIL%3B%0A%20%20%7D%0A%20%0A%20%20%2F*%20function%20for%20nth%20Fibonacci%20number%20*%2F%0A%20%20int%20fib(int%20n)%0A%20%20%7B%0A%20%20%20%20if%20(lookup%5Bn%5D%20%3D%3D%20NIL)%0A%20%20%20%20%7B%0A%20%20%20%20%20%20if%20(n%20%3C%3D%201)%0A%20%20%20%20%20%20%20%20%20%20lookup%5Bn%5D%20%3D%20n%3B%0A%20%20%20%20%20%20else%0A%20%20%20%20%20%20%20%20%20%20lookup%5Bn%5D%20%3D%20fib(n-1)%20%2B%20fib(n-2)%3B%0A%20%20%20%20%7D%0A%20%20%20%20return%20lookup%5Bn%5D%3B%0A%20%20%7D%0A%20%0A%20%20public%20static%20void%20main(String%5B%5D%20args)%0A%20%20%7B%0A%20%20%20%20Fibonacci%20f%20%3D%20new%20Fibonacci()%3B%0A%20%20%20%20int%20n%20%3D%2040%3B%0A%20%20%20%20f._initialize()%3B%0A%20%20%20%20System.out.println(%22Fibonacci%20number%20is%22%20%2B%20%22%20%22%20%2B%20f.fib(n))%3B%0A%20%20%7D%0A%20%0A%7D%0A%0A” message=”java” highlight=”” provider=”manual”/]

• Tabulation (Bottom Up): The tabulated program for a given problem builds a table in bottom up fashion and returns the last entry from table. For example, for the same Fibonacci number, we first calculate fib(0) then fib(1) then fib(2) then fib(3) and so on. So literally, we are building the solutions of subproblems bottom-up.

[ad type=”banner”]

Following is the tabulated version for nth Fibonacci Number.

Java

[pastacode lang=”java” manual=”%2F*%20Java%20program%20for%20Tabulated%20version%20*%2F%0Apublic%20class%20Fibonacci%0A%7B%0A%20%20int%20fib(int%20n)%0A%20%20%7B%0A%20%20%20%20int%20f%5B%5D%20%3D%20new%20int%5Bn%2B1%5D%3B%0A%20%20%20%20f%5B0%5D%20%3D%200%3B%0A%20%20%20%20f%5B1%5D%20%3D%201%3B%0A%20%20%20%20for%20(int%20i%20%3D%202%3B%20i%20%3C%3D%20n%3B%20i%2B%2B)%0A%20%20%20%20%20%20%20%20%20%20f%5Bi%5D%20%3D%20f%5Bi-1%5D%20%2B%20f%5Bi-2%5D%3B%0A%20%20%20%20return%20f%5Bn%5D%3B%0A%20%20%7D%0A%20%0A%20%20public%20static%20void%20main(String%5B%5D%20args)%0A%20%20%7B%0A%20%20%20%20Fibonacci%20f%20%3D%20new%20Fibonacci()%3B%0A%20%20%20%20int%20n%20%3D%209%3B%0A%20%20%20%20System.out.println(%22Fibonacci%20number%20is%22%20%2B%20%22%20%22%20%2B%20f.fib(n))%3B%0A%20%20%7D%0A%20%0A%7D%0A%2F%2F%20This%20Code%20is%20Contributed%20by%20Saket%20Kumar” message=”Java” highlight=”” provider=”manual”/]

Output:

 Fibonacci number is 34

Both Tabulated and Memoized store the solutions of subproblems. In Memoized version, table is filled on demand while in Tabulated version, starting from the first entry, all entries are filled one by one. Unlike the Tabulated version, all entries of the lookup table are not necessarily filled in Memoized version. For example, Memoized solution of the LCS problem doesn’t necessarily fill all entries.

[ad type=”banner”]