# Tag Info

11

Summary: the memoization technique is a routine trick applied in dynamic programming (DP). In contrast, DP is mostly about finding the optimal substructure in overlapping subproblems and establishing recurrence relations. Warning: a little dose of personal experience is included in this answer. Reading suggestion: If this answer looks too long to you, just ...

5

There are probably better examples, but here is one, off the top of my head: Let's say you want to check whether the edit distance between two strings $S,T$ is $\le d$, and if it is, compute the edit distance. You can use the standard dynamic programming algorithm to compute the edit distance, but "prune" the computation (stop the recursion) at any place ...

4

A general trick that works for a lot of DP problems is to look at the parameters in your recursion -- the run time is then $O(n \times max(parameter_1) \times \dots \times max(parameter_k))$ where $n$ is the number of iterations (or, the number of inputs). Consider for example a DP to solve the subset sum -- the recursion is given by $Q(i,s) := MIN(Q(i − 1,... 3 Memoization is the technique to "remember" the result of a computation, and reuse it the next time instead of recomputing it, to save time. It does not care about the properties of the computations. Dynamic programming is the research of finding an optimized plan to a problem through finding the best substructure of the problem for reusing the computation ... 3 I would like to provide 2 examples. 0-1 Knapsack problem In case of the 0-1 Knapsack problem (where W is a capacity of the knapsack and N is an amount of items), sometimes it is better to use the top-down Dynamic Programming with memoization, instead of the systematic bottom-up enumeration of entire 2D array of size WxN (especially in a case when the ... 3 There is absolutely no problem adapting dynamic programming to count solutions without regard to order (i.e., when order doesn't matter). Let$D(S,m,n)$be the number of ways to obtain a change of$n$using the first$m$coins of$S = S_1,\ldots,S_M$. We have$D(S,m,0) = 1$,$D(S,m,n) = 0$when$n < 0$, and otherwise$$D(S,m,n) = \sum_{i=1}^m D(S,i,n-S_i)... 3 As long as$f$is deterministic and depends only on its arguments (not on other global variables), yes, you can safely use that as a memoization key. The bad case cannot happen. You can see this by thinking about what happens as it reads the$t$th argument and using induction on$t$. Let$i_1,i_2,i_3,\dots,i_t$be the sequence of argument indices read (i.... 3 If your domain$X$is ordered and small, the values in$f(X)$are small as well and$f$is expensive to compute, then there's a simple reason: efficiency. For instance, if$X$is a range of natural numbers, you can store the image of$f$in an array and obtain$O(1)$-time "comptutation" of$f$at the cost of$\Theta(|X|)$memory (assuming that the size of$...

3

This sort of computation can be used for optimization purposes. A classic simple example is computing the Fibonacci sequence. Apart from the base cases, $f(n) = f(n - 1) + f(n - 2)$, but then $f(n+1) = f(n) + f(n-1)$ and $f(n+2) = f(n+1) + f(n)$, and so on. So the value of $f(n)$ for each $n$ is used repeatedly. The effect is more dramatic if you use the ...

3

There are plenty examples for which you need $\omega(1)$ time to compute each table entry or do not need to keep all table entries. An example for the former would be CYK; for the latter memoized Fibonacci and Bellman-Ford.

2

This is not a general rule. It is very possible for a dynamic programming algorithm to have greater time complexity than space complexity (but obviously not the other way around, since we spend at least $O(1)$ time per instance). For instance, you mention that the dice sum problem can be solved in $O(D*T)$ time and space (if we let $D$ be the number of dice ...

2

Consider the following counter example Let $A = aa$ Let $B = aab$ Let $Z = aabaa$ Your code will return false while the answer is true. This is because you are giving preference to matching $A$ before matching $B$. There is no property of the problem that says that it is optimal to match all characters to $A$ before $B$ in case the character can be in ...

2

You can simulate $f$ by what is known in complexity theory as a decision tree. Each node is labelled by an input $x_i$, and the edges going downwards are labelled by the possible values of $x_i$. Leaves are labelled by the output of $f$. For decision trees you can prove your claim by induction on the height of the decision tree. This reduces what you want ...

2

Let me show you the general approach to figuring this out. Then I'll let you apply that technique to your specific situation. Well, it's clear that you need to solve $A(i,j-1)$, $A(i-1,j-1)$, and $A(i-1,j+1)$ before solving $A(i,j)$. So, you need to pick an order that ensures all three of those are solved before you try to solve $A(i,j)$. What order ...

2

You can simply maintain a (hash)table, just like in the recursive case. Basically, you need to treat items on the stack like function arguments in recursion. Every time you pop items off the stack for processing, you check whether the particular entry in the table had been filled first. This gives you an equivalent memoized algorithm. Additionally, you also ...

2

Usually when trying to figure out a dynamic programming solution's time complexity, you need to find two values: The number of elements that will be calculated (or a bound on this number. Notice that "elements that would be calculated" refers to the elements you save with the memoization technique) The time it takes to process an item, assuming ...

2

Here is a simple implementation strategy. Find all three-letter truncatable words. Every three-letter word is truncatable, so this is a linear scan through the dictionary to find the three-letter words. Store them in a hashtable. Find all four-letter truncatable words. You can check whether a four-letter word wxyz is truncatable by checking whether wxy ...

1

I'm not sure I understand your question entirely, but I'm going to assume that you're talking about the space-time tradeoff. The gist of the aforementioned tradeoff is as you put it, in the context of an algorithm, the balance you have to strike between the memory it will use (its space complexity) and the time it will take to run (its time complexity). ...

1

Memoization can be applied to any function. Whether it helps with a given program or not depends on how often the function is called with the same parameters. You don't specify what your recursive solution is. Typically for this problem is imagine something like change(total, denominations) = sum of change(total - k m, denominations \ m) where m = max(...

1

From Wikipedia: There are two key attributes that a problem must have in order for dynamic programming to be applicable: optimal substructure and overlapping sub-problems. If a problem can be solved by combining optimal solutions to non-overlapping sub-problems, the strategy is called "divide and conquer" instead[1]. This is why merge sort and quick sort ...

1

In Memoization, you store the expensive function calls in a cache and call back from there if exist when needed again. This is a top-down approach, and it has extensive recursive calls. In Dynamic Programming (Dynamic Tables), you break the complex problem into smaller problems and solve each of the problems once. In Dynamic Programming, you maintain a ...

1

Your approach is correct in the sense that you produce the correct results. The book's approach has a time complexity of $O(mn)$. Since your solution doesn't use memoization and recomputes the same results repeatedly, the time complexity is much worse. In fact, your approach is functionally equivalent to the brute force method, which has a time complexity ...

1

Counting the number of Hamiltonian circuits in a graph is $\mathsf{\#P}$-hard (see for example this answer). Your problem is even harder, since we can use your problem together with binary search to count the number of Hamiltonian circuits in a given graph. As an aside, let me mention that listing things in lexicographical order might be harder than listing ...

1

This is actually a centuries-old technique that was largely killed by computers, but could possibly revive or still exist in some technical niche. It is even known to have been used by ancient Greek mathematicians and physicists. The question asks why one would prefer to tabulate the results of a function, in a table indexed by its parameters, so as to ...

1

By no means, no, your solution is not linear. It is exponencial, O(2^max(x,y)). You can see in your own picture: each function call makes another 2 calls, and that stacks multiplicatively. Now, for memoization, you would probably build a matrix and keep the records on it, in such a manner that a i,j iteration will rely only on already made calculations on x,...

1

This kind of approach is more often called dynamic programming than memoization but they are, indeed, related. In dynamic programming, however, you usually write the order in which your function is called. (This is one key difference between them.) In this case, you will clearly see that you will compute $n$ longest[i][i] first, then $n-1$ longest[i][i+1], ...

Only top voted, non community-wiki answers of a minimum length are eligible