Dynamic Programming Basics — Tabulation

  1. Memoization
  2. Tabulation

With Tabulation:

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))

--

--

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store
Teepika R M

Teepika R M

AWS Certified Big Data Specialty| Linux Certified Kubernetes Application Developer| Hortonworks Certified Spark Developer|Hortonworks Certified Hadoop Developer