Dynamic Programming Basics— Part 1

There are two methods to solve a problem using dynamic programming. In this post, we will see about 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 memoization?

To approach the problem through memoization method, first solve the given problem using recursion. Then apply memoization by saving the results in dictionary or the datastructure that suits the requirements.

Lets demonstrate the method with a simple example(not regular fibonacci sequence generation) in Scala. There are not enough resources in Scala for dynamic programming and so I hope this is helpful.

How to solve the same problem through tabulation method will be explained in dynamic programming basics — Part 2 post. Please feel free to check it.

Without Memoization:

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 since 1+1+1=3

Without memoization code explanation:

Each time the targetSum is updated by subtracting elements from the array recursively & see if at-least any one combination has resulted in 0(it means the combination can sum up-to targetSum). If so, the return value of the function is true.

The problem of using regular recursion without memoization for larger targetSum is that the runtime gets slow down or sometimes even out-of-memory execution error.

def recursion(targetSum: Int, arr: Array[Int]):Boolean={
     if(targetSum == 0) true
     else if(targetSum < 0) false
     else{
     arr.map(i=>{
     var temp=targetSum-i
     recursion(temp,arr)
     }).exists(j=>j==true)
     } 
     
recursion(7,Array(5,3,4,7))
recursion(300,Array(7,14)) // slows down the runtime

With Memoization:

With memoization code explanation:

The core logic remains the same. The difference is each time the value is computed, it is stored in the dictionary & it is reused if the value is already in the dictionary. This way, lot of re-computation can be avoided.

import scala.collection.mutable.Map
def recursion_memoized(targetSum: Int, arr: Array[Int],memo:Map[Int, Boolean]):Boolean={
if(targetSum == 0) true
else if(targetSum < 0) false
else if(memo.contains(targetSum)) memo(targetSum)
else{
 arr.map(i=>{
 var temp=targetSum-i
 memo(targetSum)=recursion_memoized(temp,arr,memo)
 memo(targetSum)
}).exists(j=>j==true)
}
}
recursion_memoized(7,Array(5,3,4,7),Map())

Conclusion:

By using memoization, we reduce the runtime, by reusing the values from the dictionary instead of recomputing the values.