[Solved]-Solving dynamic programming problems using functional programming-scala

You can see my suggestion for iterative & recursive solutions here -

https://github.com/maximn/coding-interview-questions-scala/blob/master/src/main/scala/org/questions/arrays/LongestIncreasing.scala

I don't know much about DP but I have a few observations that I hope will contribute to the conversation.

First, your example Scala code doesn't appear to solve the LIS problem. I plugged in the Van der Corput sequence as found on the Wikipedia page and did not get the designated result.

Working through the problem this is the solution I came up with.

def lis(a: Seq[Int], acc: Seq[Int] = Seq.empty[Int]): Int =
  if      (a.isEmpty)         acc.length
  else if (acc.isEmpty)       lis(a.tail, Seq(a.head))   max lis(a.tail)
  else if (a.head > acc.last) lis(a.tail, acc :+ a.head) max lis(a.tail, acc)
  else                        lis(a.tail, acc)

lis(Seq(0, 8, 4, 12, 2, 10, 6, 14, 1, 9, 5, 13, 3, 11, 7, 15)) // res0: Int = 6

This can be adjusted to return the subsequence itself, and I'm sure it can be tweaked for better performance.

As for memoization, it's not hard to roll-your-own on an as-needed basis. Here's the basic outline to memoize any arity-2 function.

def memo[A,B,R](f: (A,B)=>R): ((A,B)=>R) = {
  val cache = new collection.mutable.WeakHashMap[(A,B),R]
  (a:A,b:B) => cache.getOrElseUpdate((a,b),f(a,b))
}

With this I can create a memoized version of some often called method/function.

val myfunc = memo{(s:String, i:Int) => s.length > i}
myfunc("bsxxlakjs",7)  // res0: Boolean = true

Note: It used to be that WeakHashMap was recommended so that the cache could drop lesser used elements in memory-challenged environments. I don't know if that's still the case.