Dynamic Programming Basics — Tabulation

There are two methods to solve a problem using dynamic programming. In this post, we will see about tabulation method. Please refer to my Dynamic Programming Basics — Part 1 for Memoization method.

1. Memoization
2. Tabulation

What is dynamic programming?

It is an optimization technique over simple recursion. It greatly reduces the time taken to solve a problem for the given input. It breaks a problem into nested subproblems and computes the result for those subproblems. Those subproblems results are reused to avoid re-computation. It reduces the problem’s time complexity from exponential to polynomial. This reusing the results of subproblems can be done in two ways — memoization and tabulation.

What is tabulation?

A data-structure with definite size is initialized with default values based on the requirements and it is iterated only once to calculate the end result. At the end of the iteration, the output can be retrieved.

With Tabulation:

Problem statement: The following function takes two arguments — targetSum & an Array of Integer elements and return true if any combination of the array elements can sum up-to the targetSum. The combination can be any number(s) from the array, considered any number of times.

For eg, targetSum:3 , arr:Array(1,4,7) => returns true => 1+1+1=3

With tabulation code explanation:

Eg, table(7,Array(5,4,3))

Initialization of the Array with default values:

0 is true for any case, since targetSum 0 is possible for any combination.

Iterating over every element in the array to update the values:

For Index 0:

For Index 1:

For Index 2:

For Index 3:

For Index 4:

For Index 5:

For Index 6:

For Index 7:

The arrays are updated with values and the ones with T denotes that their index is possible with one or more elements combination(sum) in the array. The final value array(targetSum) ie, arr(7) in our example, returns the result.

def table(targetSum: Int, arr: Array[Int]):Boolean={
 val tbl: Array[Boolean]=Array.ofDim(targetSum+1)
 tbl(0)=true
 var i=0
 while(i<=targetSum){
 if(tbl(i)==true){
 arr.foreach(j=>{if (i+j <= targetSum) tbl(i+j)=true})
 }
 i=i+1
 }
 tbl(targetSum)
}
table(7,Array(9,10,7))
table(300,Array(7,14))

Conclusion:

By using tabulation, we reduce the runtime. It helps faster execution and avoids out of memory error.