# Questions tagged [memoization]

The tag has no usage guidance.

17 questions
1answer
55 views

### In which order to solve subproblems when using memoization?

I am currently trying to solve a task with memoization. I have following recursion: A (i, j) = f( A (i, j-1), A (i-1, j-1), A (i-1, j + 1) ) I am not sure in which order the sub-problems should be ...
1answer
102 views

### Can memoization be applied to any recursive algorithm?

I am new to the concepts of recursion, backtracking and dynamic programming. I am having a hard time understanding if at all I can apply memoization to a particular recursive algorithm and if there ...
3answers
927 views

### Dynamic Programming vs Memoization

I am having trouble to understand dynamic programming. Mainly because of its name. As far as I understand, it's just another name of memoization or any tricks utilizing memoization. Am I ...
1answer
171 views

### Solve longest common subsequence in a non dynamic programming way? [closed]

I am working on the longest common subsequence (LCS) problem while learning dynamic programming. Below is the Java code I created to solve the problem, which is not dynamic programming as far as I ...
1answer
250 views

### Control of the combinatorial aspects of a dynamic programming solution

I am exploring how a Dynamic Programming design approach relates to the underlying combinatorial properties of problems. For this, I am looking at the canonical instance of the coin exchange problem: ...
1answer
116 views

### Find the $k$-th lexicographically smallest hamiltonian circuit

Let's say we have given unweighted directed graph with $N$ nodes and $M$ edges, and we want to find the $K$-th hamiltonian circuit, ordered in lexicographical order. For example, if we have complete ...
0answers
124 views

### Complexity of exponential algorithm, optimised with memoization?

I was solving a problem, where one part of it was the following: "Given a m-sided dice ([1,m] values) that will be rolled n times, calculate the possibility that the total sum of rolls will be higher ...
3answers
1k views

### Memoization without array

In Cormen et al.'s Introduction to algorithms, section 15.3 Elements of dynamic programming explains memoization as follow: A memoized recursive algorithm maintains an entry in a table for the ...
0answers
80 views

### Count all possible 2-3-monotone sequences

Let $N \leq 1000$, a 2-3-monotone sequence $s$ of length $N$ is defined as: $s_i < s_{i+2}$, for $1 \leq i \leq N-2$ $s_i < s_{i+3}$, for $1 \leq i \leq N-3$ $s_i \in \{1,\dots, N\}$ Given $N$...
2answers
2k views

### With Memoization Are Time Complexity & Space Complexity Always the Same?

I am studying Dynamic Programming using both iterative and recursive functions. With recursion, the trick of using Memoization the cache results will often dramatically improve the time complexity of ...
1answer
500 views

### Shuffled Strings Dynamic Programming [closed]

So I have this question: A shuffle of two strings X and Y is formed by interspersing the characters into a new string, keeping the characters of X and Y in the same order. Example would be <...
2answers
19 views

### Can I use the set of “used arguments values” as a memoization key for a deterministic function?

I have a deterministic function $f(x_1, x_2, ..., x_n)$ that takes $n$ arguments. Given a set of arguments $X = (x_i)$, I can compute \$U_X = \{ i \in [1, n] : x_i \text{ was read during the ...
3answers
288 views

### Why would a function be tabulated in advance and then retrieved?

Given some function and assuming no concern for the time to compute the co-domain for its domain, when might it be preferable to compute and tabulate in advance the co-domain results of the function, ...
1answer
592 views

### Runtime of a recursive algorithm

I have a simple recursive solution as below: ...
0answers
37 views

### What kinds of recurrence relations can be involved in a tabulation solution?

We all know F(n) = F(n-1) + F(n-2) is an easy example. We can compute this by using DP. But what about F(n) = F(n-1) + k, we could compute this by tabulation but would you still call it DP? Also, ...
1answer
2k views

### Upper Bound on Runtime of Memoized DP Algorithms

I find it fairly easy to generate an upper bound for nearly any iterative solution (e.g. look at the limits on each loop, etc.), and can oftentimes create an upper bound for normal recursive functions....
1answer
1k views

### Memoized Palindrome Subsequence

I am trying to find the maximum palindrome sub-sequence and after going through some tutorials, I came up with a memoized version.But I am not sure about the runtime.I want to know if the following ...