Questions tagged [memoization]
A technique in which function return values are saved so they do not need to be recalculated if the function is called again with the same arguments.
40 questions
1
vote
1
answer
91
views
Memoization of complete states
Would it be possible to do memoization on complete states of a computer? In other words, would it be possible to map out complete states (of a program or OS) and then memoize them to have a speedup of ...
- 11
0
votes
2
answers
85
views
What is the complexity of this tree recursive integer replacement algorithm?
LeetCode has an Integer Replacement problem defined as follows:
Given a positive integer $n$, you can apply one of the following operations:
If $n$ is even, replace $n$ with $n / 2$.
If $n$ is odd, ...
- 1,592
0
votes
1
answer
1k
views
Counting Towers Recurrence Verification From CSES Problem Set
Problem Statement:
Your task is to build a tower whose width is 2 and height is n. You have an unlimited supply of blocks whose width and height are integers.
For example, here are some possible ...
- 1
0
votes
0
answers
62
views
Calculating Runtime Complexity: Recursion + Memoization vs Dynamic Programming (with example)
For cases where recursion is used as well as memoization (so that a number of subtrees of what would otherwise be the overall recursive call tree are each replaced to be ...
- 101
2
votes
2
answers
457
views
Zero sum game: dp recursion strategy
Trying to solve the zero-sum problem described here, where two opponent players at each turn can choose to collect 1, 2 or 3 stones with different values, with the objective of getting more points at ...
- 121
0
votes
0
answers
34
views
Defining dynamic programming [duplicate]
Could we say that Dynamic programming is nothing but recursion + Memoization?
Although the formal definition of dynamic programming is that the problem should have an optimal substructure property, ...
- 143
1
vote
1
answer
308
views
Time complexity analysis for dynamic programming using memoization
I am trying to figure out the time complexity for "Regular Expression Matching" problem.
Problem statement is simple, only meta characters allowed are '.' and '*'. Actual problem statement ...
-1
votes
1
answer
163
views
Finding the number of ways to reach a particular position in a grid from a starting position (given some cells which are blocked)
I came across this question in a job interview and I couldn't solve it.
In a n*m matrix some cells are blocked.The robot can only move in direction of (x-1,y+2) or <...
0
votes
1
answer
184
views
Speed up counting the number of A[i] * A[j] * A[k] = A[l] where i < j < k < l
I recently got onto the following problem: we consider the following array:
A = [2, 3, 6, 1, 6, 4, 12, 24]
we need to count the number of times these two ...
- 1
1
vote
1
answer
404
views
How to convert any recursive solution to a Dynamic programming table? Is there any tricks/tips to follow?
I've been able to form a recurrence relation with memoization in a recursive approach for most problems but the online coding rounds exceed the time limit or stack overflow occurs in all these ...
- 111
3
votes
1
answer
161
views
What's the runtime complexity of this algorithm for breaking up string into words?
I am given a input string $s$ ("bedbathandbeyond") and a set of words {"bed", "bath", "beyond", "bat", "hand", "and"}. I need to ...
- 33
1
vote
0
answers
172
views
Sub-matrix with minimum size of $k$ and minimum sum
We have an $n \times m$ matrix whose entries are non-negative integers and we want to find a sub-matrix whose area (number of entries) is at least $k$ such that the sum of the entries in minimal. The ...
- 111
1
vote
1
answer
230
views
Time Complexity of Memoized Solution
I was solving Stone Game II on LeetCode. I was able to come up with a recursive (TLE) solution, which I optimized using memoization. The recursive solution computes a function $u(i,m)$, depending on ...
- 111
0
votes
0
answers
562
views
Why the time complexity for following pseudocode is O(n^2)?
So, I was going through the Rod-Cutting problem in the Dynamic Programming section of the Introduction to Algorithms by CLRS.
Here's the rod-cutting problem statement: Given a rod of length n inches ...
3
votes
1
answer
787
views
How to convert a recursive function to a non recursive one using stack while keeping memoization?
Let's say I want to count the number of ways a string can be decoded, once encoding algorithm follows this map: 'a'=>'1', 'b'=>'2', ... 'z'=>'26'.
I could ...
- 31