score:1

score:3

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.