Questions tagged [memoization]
The memoization tag has no usage guidance.
10
questions with no upvoted or accepted answers
2
votes
2
answers
396
views
Runtime of weighted interval scheduling dynamic programming algorithm
Consider this implementation of a dynamic programming algorithm for weighted interval scheduling:
...
- 435
1
vote
0
answers
116
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
0
answers
30
views
Is Constant Folding a type of Memoization?
I was reading about Constant Folding and it sounds very similar to Memoization so I suspect that it indeed is a type of memoization but I've done some searching and can't find a solid answer (in ...
- 111
1
vote
0
answers
82
views
How does the asterisk (*) work in the wildcard matching problem?
This is a wildcard matching problem. Given a pattern P containing letters and character * that can match an arbitrary string of characters (including an empty string), my task is to write a polynomial-...
- 21
1
vote
0
answers
83
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$...
- 139
1
vote
1
answer
122
views
Can the algorithm be optimized?
I am new to backtracking and recursion. I have seen numerous explanations on how on to find the minimum number of coins needed to make a particular amount. This involves a top down dynamic approach ...
- 131
0
votes
0
answers
41
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
0
votes
0
answers
481
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 ...
- 243
0
votes
0
answers
210
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 ...
- 163
0
votes
0
answers
88
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, ...
- 101