I wanted to memoize this:

    def fib(n: Int) = if(n &lt;= 1) 1 else fib(n-1) + fib(n-2)
    println(fib(100)) // times out

So I wrote this and this surprisingly compiles and works (I am surprised because `fib` references itself in its declaration):

    case class Memo[A,B](f: A =&gt; B) extends (A =&gt; B) {
      private val cache = mutable.Map.empty[A, B]
      def apply(x: A) = cache getOrElseUpdate (x, f(x))
    }
    
    val fib: Memo[Int, BigInt] = Memo {
      case 0 =&gt; 0
      case 1 =&gt; 1
      case n =&gt; fib(n-1) + fib(n-2) 
    }

    println(fib(100))     // prints 100th fibonacci number instantly

But when I try to declare fib inside of a `def`, I get a compiler error:

    def foo(n: Int) = {
      val fib: Memo[Int, BigInt] = Memo {
        case 0 =&gt; 0
        case 1 =&gt; 1
        case n =&gt; fib(n-1) + fib(n-2) 
      }
      fib(n)
    } 

Above fails to compile `error: forward reference extends over definition of value fib
case n =&gt; fib(n-1) + fib(n-2)`

Why does declaring the `val fib` inside a def fails but outside in the class/object scope works?

To clarify, why I might want to declare the recursive memoized function in the def scope - here is my solution to the subset sum problem:

  

    /**
       * Subset sum algorithm - can we achieve sum t using elements from s?
       *
       * @param s set of integers
       * @param t target
       * @return true iff there exists a subset of s that sums to t
       */
      def subsetSum(s: Seq[Int], t: Int): Boolean = {
        val max = s.scanLeft(0)((sum, i) =&gt; (sum + i) max sum)  //max(i) =  largest sum achievable from first i elements
        val min = s.scanLeft(0)((sum, i) =&gt; (sum + i) min sum)  //min(i) = smallest sum achievable from first i elements
    
        val dp: Memo[(Int, Int), Boolean] = Memo {         // dp(i,x) = can we achieve x using the first i elements?
          case (_, 0) =&gt; true        // 0 can always be achieved using empty set
          case (0, _) =&gt; false       // if empty set, non-zero cannot be achieved
          case (i, x) if min(i) &lt;= x &amp;&amp; x &lt;= max(i) =&gt; dp(i-1, x - s(i-1)) || dp(i-1, x)  // try with/without s(i-1)
          case _ =&gt; false            // outside range otherwise
        }
    
        dp(s.length, t)
      }

Is there a generic way to memoize in Scala?

**[Link to the original problem][1]**

It&#39;s not a homework question. I just thought that someone might know a real solution to this problem.

I was on a programming contest back in 2004, and there was this problem:

&gt; Given n, find sum of digits of n!. n can be from 0 to 10000. Time limit: 1 second. I think there was up to 100 numbers for each test set.

My solution was pretty fast but not fast enough, so I just let it run for some time. It built an array of pre-calculated values which I could use in my code. It was a hack, but it worked.

But there was a guy, who solved this problem with about 10 lines of code and it would give an answer in no time. I believe it was some sort of dynamic programming, or something from number theory. We were 16 at that time so it should not be a &quot;rocket science&quot;. 

Does anyone know what kind of an algorithm he could use?

**EDIT**: I&#39;m sorry if I didn&#39;t made the question clear. As mquander said, there should be a clever solution, without bugnum, with just plain Pascal code, couple of loops, O(n&lt;sup&gt;2&lt;/sup&gt;) or something like that. 1 second is not a constraint anymore.

I found [here][2] that if n &gt; 5, then 9 divides sum of digits of a factorial. We also can find how many zeros are there at the end of the number. Can we use that?

Ok, another problem from programming contest from Russia. Given 1 &lt;= N &lt;= 2 000 000 000, output N! mod (N+1). Is that somehow related?


  [1]: http://acm.uva.es/p/v102/10220.html
  [2]: http://research.att.com/~njas/sequences/A004152

Sum of digits of a factorial

I am working on this problem:

&gt; The Subset Sum problem takes as input a set `X = {x1, x2 ,…, xn}` of `n` integers and another integer `K`. The problem is to check if there exists a subset `X&#39;` of `X` whose elements sum to `K` and finds the subset if there&#39;s any. For example, if `X = {5, 3, 11, 8, 2}` and `K = 16` then the answer is `YES` since the subset `X&#39; = {5, 11}` has a sum of `16`. Implement an algorithm for Subset Sum whose run time is at least `O(nK)`.

Notice complexity `O(nK)`. I think dynamic programming may help.

I have found an exponential time algorithm, but it doesn&#39;t help.

Can someone help me solve this problem?

Subset Sum algorithm

What is **dynamic programming**? 

How is it different from recursion, memoization, etc? 

I have read the [wikipedia article][1] on it, but I still don&#39;t really understand it.


  [1]: http://en.wikipedia.org/wiki/Dynamic_programming

What is dynamic programming?

The **bottom-up** approach (to dynamic programming) consists in first looking at the &quot;smaller&quot; subproblems, and then solve the larger subproblems using the solution to the smaller problems.

The **top-down** consists in solving the problem in a &quot;natural manner&quot; and check if you have calculated the solution to the subproblem before.

I&#39;m a little confused. What is the difference between these two?

What is the difference between bottom-up and top-down?

I have a set of integers. I want to find the [longest increasing subsequence][1] of that set using dynamic programming.


  [1]: https://en.wikipedia.org/wiki/Longest_increasing_subsequence

How to determine the longest increasing subsequence using dynamic programming?

What is the difference between Divide and Conquer Algorithms and Dynamic Programming Algorithms? How are the two terms different? I do not understand the difference between them.

Please take a simple example to explain any difference between the two and on what ground they seem to be similar.




Difference between Divide and Conquer Algo and Dynamic Programming

Imagine you&#39;re in a tall building with a cat. The cat can survive a fall out of a low story window, but will die if thrown from a high floor. How can you figure out the longest drop that the cat can survive, using the least number of attempts?

Obviously, if you only have one cat, then you can only search linearly. First throw the cat from the first floor. If it survives, throw it from the second. Eventually, after being thrown from floor f, the cat will die. You then know that floor f-1 was the maximal safe floor.

But what if you have more than one cat? You can now try some sort of logarithmic search. Let&#39;s say that the build has 100 floors and you have two identical cats. If you throw the first cat out of the 50th floor and it dies, then you only have to search 50 floors linearly. You can do even better if you choose a lower floor for your first attempt. Let&#39;s say that you choose to tackle the problem 20 floors at a time and that the first fatal floor is #50. In that case, your first cat will survive flights from floors 20 and 40 before dying from floor 60. You just have to check floors 41 through 49 individually. That&#39;s a total of 12 attempts, which is much better than the 50 you would need had you attempted to use binary elimination.

**In general, what&#39;s the best strategy and it&#39;s worst-case complexity for an n-storied building with 2 cats? What about for n floors and m cats?**

Assume that all cats are equivalent: they will all survive or die from a fall from a given window. Also, every attempt is independent: if a cat survives a fall, it is completely unharmed.

This isn&#39;t homework, although I may have solved it for school assignment once. It&#39;s just a whimsical problem that popped into my head today and I don&#39;t remember the solution. Bonus points if anyone knows the name of this problem or of the solution algorithm.

Throwing cats out of windows

I know that `Knapsack` is NP-complete while it can be solved by DP. They say that the DP solution is `pseudo-polynomial`, since it is exponential in the &quot;length of input&quot; (i.e. the numbers of bits required to encode the input). Unfortunately I did not get it. Can anybody explain that `pseudo-polynomial` thing to me slowly ?

Why is the knapsack problem pseudo-polynomial?

I&#39;d like to compare 2 strings and keep the matched, splitting off where the comparison fails.

So if I have 2 strings -

    string1 = apples
    string2 = appleses

    answer = apples


Another example, as the string could have more than one word. 

    string1 = apple pie available
    string2 = apple pies

    answer = apple pie


I&#39;m sure there is a simple Python way of doing this but I can&#39;t work it out, any help and explanation appreciated.




Find common substring between two strings

I am looking for a manageably understandable example for someone who wants to learn Dynamic Programming. [There are nice answers here about what is dynamic programming][1]. The fibonacci sequence is a great example, but it is too small to scratch the surface. It looks a great subject to learn about although I haven&#39;t taken the algorithms class yet, hopefully it is on my list for the spring.

  [1]: https://stackoverflow.com/questions/1065433/what-is-dynamic-programming

A simple example for someone who wants to understand Dynamic Programming

There is a grid of size **N x M**. Some cells are *islands* denoted by &#39;0&#39; and the others are *water*. Each water cell has a number on it denoting the cost of a bridge made on that cell. You have to find the minimum cost for which all the islands can be connected. A cell is connected to another cell if it shares an edge or a vertex.

What algorithm can be used to solve this problem? What can be used as a brute force approach if the values of N, M are very small, say NxM &lt;= 100?

*Example*: In the given image, green cells indicate islands, blue cells indicate water and light blue cells indicate the cells on which a bridge should be made. Thus for the following image, the answer will be **17**.

![http://i.imgur.com/ClcboBy.png](http://i.imgur.com/ClcboBy.png)

Initially I thought of marking all the islands as nodes and connecting every pair of islands by a shortest bridge. Then the problem could be reduced to Minimum spanning tree, but in this approach I missed the case where edges are overlapping. *For example*, in the following image, the shortest distance between any two islands is **7** (marked in yellow), so by using Minimum Spanning Trees the answer would be *14*, but the answer should be **11** (marked in light blue).

![image2](http://i.imgur.com/5az6ii8.png)


What is the minimum cost to connect all the islands?

**Input**: A 2-dimensional array NxN - Matrix - with positive and negative elements.&lt;br&gt;&lt;br&gt;**Output**: A submatrix of any size such that its summation is the maximum among all possible submatrices.

**Requirement**: Algorithm complexity to be of **O(N^3)**&lt;br&gt;

**History:** With the help of the Algorithmist, Larry and a modification of Kadane&#39;s Algorithm, i managed to solve the problem **partly** which is determining the summation only - below in Java.&lt;br&gt;
Thanks to **Ernesto** who managed to solve the rest of the problem which is determining the boundaries of the matrix i.e. top-left, bottom-right corners - below in Ruby.

Getting the submatrix with maximum sum?

For example, let the string be the first 10 digits of pi, `3141592653`, and the subsequence be `123`. Note that the sequence occurs twice:

    3141592653
     1    2  3
       1  2  3


This was an interview question that I couldn&#39;t answer and I can&#39;t think of an efficient algorithm and it&#39;s bugging me. I feel like it should be possible to do with a simple regex, but ones like `1.*2.*3` don&#39;t return every subsequence. My naive implementation in Python (count the 3&#39;s for each 2 after each 1) has been running for an hour and it&#39;s not done.

Find the number of occurrences of a subsequence in a string

&gt; **Possible Duplicate:**  
&gt; [Dynamic programming and memoization: top-down vs bottom-up approaches](https://stackoverflow.com/questions/6164629/dynamic-programming-and-memoization-top-down-vs-bottom-up-approaches)  

&lt;!-- End of automatically inserted text --&gt;

I have gone through a lot of articles on this but can&#39;t seem to make sense of it. At times recursion and dynamic programming looks the same and at others memoization &amp; dynamic programming look alike. Can someone explain to me what&#39;s the difference?

P.S. It will also be helpful if you could point me to some code using the three approaches on the same problem. (e.g. the Fibonacci series problem, I think every article I read used recursion but referred to it as dynamic programming)

What&#39;s the difference between recursion, memoization &amp; dynamic programming?

In programming contests, the following pattern occurs in a lot of tasks:

&gt; Given numbers A and B that are huge (maybe 20 decimal digits or more), determine the number of integers X with A ≤ X ≤ B that have a certain property P

[SPOJ has lots of tasks like these](https://www.google.com/?q=%22spoj%22+%22numbers+between%22+A+and+B#q=%22spoj%22+%22numbers+between%22+A+and+B) for practice.

Where examples of interesting properties include:

* &quot;the digit sum of X is 60&quot;
* &quot;X consists only of the digits 4 and 7&quot;
* &quot;X is palindromic&quot;, which means that the decimal representation of X equals its reverse (for example, X = 1234321)

I know that if we define *f(Y)* to be the number of such integers X ≤ Y, then the answer to our question is *f(B) - f(A - 1)*. The reduced problem is how to compute the function *f* efficiently. In some cases we can make use of certain mathematical properties to come up with a formula, but often the properties are more complicated and we don&#39;t have enough time for that in a contest.

Is there a more general approach that works in a lot of cases? And can it also be used to enumerate the numbers with the given property or compute some aggregation on them?

A variation of this is to find the k-th number with a given property, which of course can be solved by using binary search together with a counting function.

How to count integers between large A and B with a certain property?

What is the difference between memoization and dynamic programming? I think dynamic programming is a subset of memoization. Is it right?

All Dynamic Programming Solutions on Gang of Coders

Total of 17 Dynamic Programming Solutions