Subset Sum is the first NP-complete problem I learned at Macalester. This question is viewed 36000+ times yet I don’t see a sufficient answer that explains the algorithm in detail with logic. So I thought I make an attempt to do so. Assumption: For the sake of simplicity first I made the assumption that the … Read more
I found a better way to memoize using Scala: def memoize[I, O](f: I => O): I => O = new mutable.HashMap[I, O]() { override def apply(key: I) = getOrElseUpdate(key, f(key)) } Now you can write fibonacci as follows: lazy val fib: Int => BigInt = memoize { case 0 => 0 case 1 => 1 … Read more
Indeed, there is an approach to this pattern which turns out to work quite often. It can also be used to enumerate all the X with the given property, provided that their number is reasonably small. You can even use it to aggregate some associative operator over all the X with the given property, for … Read more
This is a classical dynamic programming problem (and not typically solved using regular expressions). My naive implementation (count the 3’s for each 2 after each 1) has been running for an hour and it’s not done. That would be an exhaustive search approach which runs in exponential time. (I’m surprised it runs for hours though). … Read more
Here’s an explanation to go with the posted code. There are two key tricks to make this work efficiently: (I) Kadane’s algorithm and (II) using prefix sums. You also need to (III) apply the tricks to the matrix. Part I: Kadane’s algorithm Kadane’s algorithm is a way to find a contiguous subsequence with maximum sum. … Read more
Consider calculating the fibonacci sequence: Pure recursion: int fib(int x) { if (x < 2) return 1; return fib(x-1) + fib(x-2); } results in exponential number of calls. Recursion with memoization/DP: int fib(int x) { static vector<int> cache(N, -1); int& result = cache[x]; if (result == -1) { if (x < 2) result = 1; … Read more
To approach this problem, I would use an integer programming framework and define three sets of decision variables: x_ij: A binary indicator variable for whether we build a bridge at water location (i, j). y_ijbcn: A binary indicator for whether water location (i, j) is the n^th location linking island b to island c. l_bc: … Read more
Check out this site: Dynamic Programming Practice Problems
For completeness, difflib in the standard-library provides loads of sequence-comparison utilities. For instance find_longest_match which finds the longest common substring when used on strings. Example use: from difflib import SequenceMatcher string1 = “apple pie available” string2 = “come have some apple pies” match = SequenceMatcher(None, string1, string2).find_longest_match() print(match) # -> Match(a=0, b=15, size=9) print(string1[match.a:match.a + … Read more
The running time is O(NW) for an unbounded knapsack problem with N items and knapsack of size W. W is not polynomial in the length of the input though, which is what makes it pseudo-polynomial. Consider W = 1,000,000,000,000. It only takes 40 bits to represent this number, so input size = 40, but the … Read more