Comment by florianj

How did you use DP for scenario 2 and 3? The table seems to be way to big unless you do some optimizations.

Also did you optimize for the best case in any way vs expected cases?