Skip to main content

Questions tagged [memoization]

The tag has no usage guidance.

Filter by
Sorted by
Tagged with
0 votes
2 answers
40 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, ...
Ellen Spertus's user avatar
0 votes
1 answer
194 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 ...
Ved K's user avatar
  • 1
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 ...
mishar's user avatar
  • 101
2 votes
2 answers
216 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 ...
rickyviking's user avatar
0 votes
0 answers
30 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, ...
nicku's user avatar
  • 143
1 vote
1 answer
202 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 ...
Siddhartha Sadhukhan's user avatar
-1 votes
1 answer
125 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 <...
Amelia Levi's user avatar
0 votes
1 answer
125 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 ...
Tel0s's user avatar
  • 1
1 vote
1 answer
320 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 ...
arjunsiva's user avatar
  • 111
3 votes
1 answer
114 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 ...
AndresArpi's user avatar
1 vote
0 answers
121 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 ...
Pegi's user avatar
  • 111
1 vote
1 answer
177 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 ...
Tyler Durden's user avatar
0 votes
0 answers
488 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 ...
KhiladiBhaiyya's user avatar
3 votes
1 answer
686 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 ...
Yago Tomé's user avatar
2 votes
1 answer
2k views

How do I calculate the time complexity of this memoized algorithm?

The problem is: count all increasing subsequence of s. ...
Naruto Uzumaki's user avatar
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 ...
Spindoctor's user avatar
2 votes
2 answers
490 views

Runtime of weighted interval scheduling dynamic programming algorithm

Consider this implementation of a dynamic programming algorithm for weighted interval scheduling: ...
kanso37's user avatar
  • 435
1 vote
0 answers
31 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 ...
Alex W's user avatar
  • 111
4 votes
2 answers
92 views

Algorithm to find "truncatable words"?

My son who is just learning to read loves the concept of hiding one letter of a word with his finger and asking what the rest of the word spells. His favorite is turning "her" into "he" and "then" ...
user112052's user avatar
1 vote
0 answers
85 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-...
amV's user avatar
  • 21
0 votes
2 answers
72 views

An underestimated tradeoff between Memory and the Effectivity of Computation?

Is there a theorem / single formula, that describes the often necessary tradeoff between memoiziation (for example that of a certain variable x) and effective computation as written in any common form ...
SomeGuy's user avatar
0 votes
1 answer
351 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 ...
user650708's user avatar
2 votes
1 answer
845 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 ...
Spindoctor's user avatar
18 votes
4 answers
21k 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 ...
Eonil's user avatar
  • 301
2 votes
0 answers
1k views

Find worst-time complexity for a problem on matching a simple regular expression? [duplicate]

I am not looking for the complexity of following algorithm but rather how to think about the problem and calculate complexity of a given solution? One way is to perhaps use The Master Method for ...
Uthman's user avatar
  • 121
1 vote
1 answer
1k 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 ...
yimcai's user avatar
  • 23
1 vote
1 answer
812 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: ...
Eduardo J. Sanchez's user avatar
2 votes
1 answer
342 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 ...
someone12321's user avatar
  • 1,428
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 ...
Dimos's user avatar
  • 163
14 votes
3 answers
2k 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 ...
Pece's user avatar
  • 311
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$...
shisui's user avatar
  • 139
2 votes
2 answers
4k 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 ...
Fairly Nerdy's user avatar
1 vote
1 answer
935 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 <...
curious's user avatar
  • 11
2 votes
2 answers
20 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 ...
Jean Hominal's user avatar
1 vote
3 answers
608 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, ...
gallygator's user avatar
0 votes
1 answer
1k views

Runtime of a recursive algorithm

I have a simple recursive solution as below: ...
Anurag Kapur's user avatar
0 votes
0 answers
90 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, ...
Dinesh Babu K G's user avatar
2 votes
1 answer
3k 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....
apnorton's user avatar
  • 254
1 vote
1 answer
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 ...
Sid's user avatar
  • 355