Questions tagged [memoization]
In computing, memoization is an optimization technique used primarily to speed up computer programs by having function calls avoid repeating the calculation of results for previously-processed inputs.
1,494
questions
1
vote
1
answer
72
views
Issue with implementation of longest common subsequence
I'm doing this challenge: https://leetcode.com/problems/longest-common-subsequence/
I've tried a number of ways to debug my code, but I can't figure out what's wrong.
Like in my head the way I ...
0
votes
0
answers
40
views
Longest Stable Subsequence - Recover solution from memo table
I am working on a DP problem to find longest stable subsequence, and I'm currently stuck with recovering the solution.
Here is the problem statement
I have tried the below solution,
def computeLSS(a):...
0
votes
1
answer
27
views
How can I use recursion and memoization to understand whether the a string is a combination of other two strings?
Consider 2 strings:
a = "wxy"
b = "mnop"
z = "wmxnoyp"
string z is a mixedstring if it is a combination of string a and b such that the length of string z is equal to ...
1
vote
1
answer
54
views
DP array 0th element is initialized as 1 instead of 0
I encountered the LeetCode climbStairs problem:
You are climbing a staircase. It takes n steps to reach the top.
Each time you can either climb 1 or 2 steps. In how many distinct ways can you climb ...
0
votes
1
answer
139
views
Rule react-hooks/exhaustive-deps and over-optimization with useCallback
There are a lot of post about the eslint rule react-hooks/exhaustive-deps, and also about the good usage of the memoizations hooks useMemo and useCallback which are generally way overused, but I haven'...
0
votes
0
answers
56
views
Dynamic programming with memoization on the rob house problem
This is my problem I'm working on:
" You are a professional robber planning to rob houses along a street. The houses are numbered
0, 1, 2, ..., and you my assume that the number of houses is at ...
6
votes
3
answers
421
views
NextJS 13 Fetch Request Memoization
I am working on a React project with NextJS 13 and I have problems with using request memoization for fetch. It always sends request to backend even in the same request.
I have a simple endpoint at ...
0
votes
3
answers
66
views
Re-render issue while using useMemo hooks
const sum = useMemo(() => a + b, [a, b])
What will happen when a and b are interchanged ?
Like if a = 5, b = 10 in the current render. What will happen when a = 10, b = 5? Will it re-render after ...
1
vote
1
answer
359
views
How to optimize the rendering of a large list of items in React?
I have a React component that renders a large list of items (about 1000) using the map method. Each item is a complex component that has its own state and props, and can be updated by the user. The ...
-1
votes
1
answer
119
views
"Coin change 2": Why is this dynamic programming implementation not efficient enough? [closed]
I am working on a LeetCode problem, 518. Coin Change II:
You are given an integer array coins representing coins of different denominations and an integer amount representing a total amount of money.
...
1
vote
0
answers
20
views
Inconsistent output on leetcode and vs code [duplicate]
class Solution:
def combinationSum4(self, nums: List[int], target: int,memo={}) -> int:
if target in memo:
return memo[target]
if target==0:
return 1
...
1
vote
1
answer
44
views
Is there any reason to memoize Redux action creators in React?
My coworker has stated that articles he's found have pointed to performance increases when memoizing Redux action creators in React, but I've not found anything that supports that and I can't really ...
0
votes
1
answer
109
views
Ideal Profits in companies in Perfect Binary Search tree
I'm trying to solve the following problems here:
In the X world, companies have a hierarchical structure to form a large binary tree network (can be assumed to be a perfect binary tree). Thus every ...
0
votes
1
answer
47
views
Returning the last computed result in a throttled function
I am working on a exercise based of the underscore _.throttle function. Our function is slightly modified as we have the return the last computed result if the _.throttle function is still waiting to ...
-1
votes
1
answer
47
views
Is there a difference between my code and the one explicitly using Memoization?
I tried to implement an efficient function to return the Fibonacci value for a given index. Once I discovered the cons of implementing a basic/simple recursion function to return the Fibonacci series, ...
0
votes
1
answer
49
views
Python acting in a strange way (Dynamic Programing) [duplicate]
I have written this following code that takes an integer N and and array of integers: arr. The task is to find the shortest combination of the integers in arr that sum up to N . Each elements of arr ...
0
votes
1
answer
54
views
Printing minimum path sum path (matrix)
Solving [leetcode problem][1] which is as follow:
Given a m x n grid filled with non-negative numbers, find a path from top left to bottom right, which minimizes the sum of all numbers along its path.
...
1
vote
1
answer
103
views
Does it make sense to replace ternary operator with a React useMemo function
I am having a ternary operator inside my React prop:
const isItemOne = item.type === 'Item one';
return (
<ChildComponent
myProp={
isItemOne
? generateFunctionOne(itemOne.id, ...
0
votes
0
answers
37
views
Purpose of nested function within memoization function is confusing me. Does someone smart understand?
What is the function 'inner' doing below? Is it there just because the 'return inner' needs to be enclosed within the 'memoize_factorial' function?
memory = {}
def memoize_factorial(f):
# ...
1
vote
1
answer
76
views
Haskell question about memoization / evalution
I am trying to write a "how to make amount with access to coins to denominations coins, using the fewest coins" function in Haskell. I implemented this with DFS, which works but is quickly ...
1
vote
3
answers
62
views
Trying to implement memoization fibonacci series, it works till fib(46), but after that its returning negative values
I am trying to implement a dynamic programming problem for getting the nth number in the fibbonacci series. I am getting the output till 46th element but after that i am getting negative numbers as ...
0
votes
1
answer
129
views
React functional component behaviour question
I'm starting to learn React and its components, specifically the functional components.
While playing around with the code i found out a particular behavior that left me with a doubt/question. I'm ...
0
votes
1
answer
99
views
Problem in Memoization part! Leetcode problem 121. Best Time to Buy and Sell Stock
I was trying to solve this problem, I know it can be done by one simple for loop but I wanna try doing it using dp.
So can anyone help in the memoization part?
Problem:
You are given an array prices ...
0
votes
2
answers
103
views
How to convert the following backtracking code into a top down head recursive memoized version?
I am trying to solve the famous Coin Change problem, below is the problem statement!!
Coin Change II
You are given an integer array coins representing coins of different denominations and an integer ...
0
votes
1
answer
36
views
Error in output in Bestsum Memoization problem
So I was doing this sum, and could not get the correct output for particular cases.
def bestsum(targetsum,numbers,memo={}):
if targetsum in memo:
return memo[targetsum]
if targetsum==...
0
votes
0
answers
26
views
canConstruct memoization giving wrong output
I was trying to memoize the canConstruct function, that takes target string and wordBank as inputs and this function checks if the given target string can be formed using the words given in the ...
0
votes
1
answer
74
views
Array of HashMap vs just HashMap
I am practicing on dynamic programming problems and often use a HashMap<(usize, i32), i32> with a key being a tuple of an index and variable for top-down (memoization). However, since all ...
0
votes
0
answers
40
views
How to replace a powershell function and call the old version?
I am trying to replace a powershell function and with a new one and then call the oldone from withing, but I am having little luck.
In my usecase I want to add caching to some webrequests. So i've ...
1
vote
0
answers
74
views
Longest Increasing Subsequence - LeetCode 300
Referring to the question: Longest Increasing Subsequence
Here is my code with recursion that works but is too slow as it is not doing memoization:
class Solution {
public static int recurse(int prev, ...
0
votes
1
answer
46
views
Memoization+Recursion and DP array filling order
I have solved the below problem with recursion and memoization.
**Given a string s. In one step you can insert any character at any index of the string.
Return the minimum number of steps to make s ...
-10
votes
1
answer
260
views
Node.js vs. Rust, but Node.js is faster [closed]
I have a function named
grid
which is from the dynamic programming problem "grid Traveler". I wrote the same function twice in JavaScript and Rust and benchmarked 10 million calculations ...
0
votes
1
answer
47
views
Further optimization to the algo for interleaving string
I am trying to solve LeetCode problem 97. Interleaving String
:
Given three strings s1, s2 and s3, write a program that checks whether s3 is an interleaving of s1 and s2.
Problem Note:
S3 is said to ...
1
vote
4
answers
211
views
Efficient implementation of the N fibonacci numbers using complex algorithm
I am looking for an even faster method of calculating the first N fibonacci numbers. I am already aware of the recursive method of solving this problem using memoization as well as the simpler method ...
2
votes
1
answer
55
views
Memoization with recursion slower than just recursion
I'm trying to understand time complexity-wise what to expect running fibonacci with recursion vs. recursion with memoization & recursion.
I expect using only recursion - (2^n) - to be slower than ...
4
votes
2
answers
106
views
Performance difference of function and data recursion in Haskell
While thinking about this other question, I realized that the following functions smoothSeq and smoothSeq'
smoothSeq :: (Integer, Integer, Integer) -> [Integer]
smoothSeq (a, b, c) = result
where
...
1
vote
0
answers
382
views
My react native app is slower and even slower with react navigation
My react native app is slow. It takes about 5-6 seconds to render first screen of application. And navigation between screens is even worse.
react-native: 0.71.3
@react-navigation/bottom-tabs: 6.5.7
@...
-1
votes
1
answer
74
views
Why does timeit results in almost constant time for all memoization runs?
We compute the Fibonacci number:
def fibo_memo(i, memo={}):
if i <= 0:
return 0
elif i == 1:
return 1
elif i in memo:
return memo[i]
else:
memo[i] = ...
0
votes
1
answer
46
views
Memoization of recursive calls on separate lines
I am attempting to solve Leetcode problem 70 by first trying to visualize the tree and then implement the solution. The tree is simple in that the left branch is a single step and the second branch is ...
2
votes
2
answers
178
views
Not able to clear Javascript Memoized function cache
I am trying to clear the memoized cache object but tried different solutions like prototype, call and bind but not able to make it work. Any help would be appreciated.
function memoize(func) {
let ...
0
votes
1
answer
49
views
React+Typescript how do I use the same event to update memoized state?
I am making a teaching-related app that fetches questions from a backend. I memoize the question fetching process in a custom useMemo hook so that the state updates caused by entering the answer doesn'...
0
votes
3
answers
97
views
Why is my memoization decorator not working for the Ackermann function?
I wrote a decorator that can memoize functions, here's how it looks like:
def memoizator(func):
cache = {}
def wrapper(*args):
if args not in cache:
cache[args] = func(*...
1
vote
0
answers
131
views
Zustand causing rerender even when state updates to identical item
I am using zustand for some state management. I notice with zustand, that if you update a state variable, to a clone of the exact copy of that value, I get a rerender. For example:
// The zustand ...
1
vote
0
answers
44
views
What is the memoisation problem in this recursive algorithm that I cannot see?
I'm learning about data structures and algorithms via Structy.com's course, I'm trying to solve this problem, given a target sum and an array of numbers, can any sum of any combination of the numbers ...
0
votes
0
answers
92
views
Memoizing both useState and mobx observable dependent state
I have store with currencies. It stores array of currency info objects. It is initialised on load of page and might be updated during user activities. The store has method currencies....
1
vote
1
answer
46
views
I want to optimize my solution using memoization. Can someone help me?
By starting with an empty string, we can perform either of the following:
Append the character '0' zero times.
Append the character '1' one times.
Given low and high as the minimum and maximum ...
0
votes
0
answers
35
views
What is the time complexity of this recursion with memoization code?
public class Solution {
public boolean wordBreak(String s, List<String> wordDict) {
return wordBreakMemo(s, new HashSet<>(wordDict), 0, new Boolean[s.length()]);
}
// ...
0
votes
2
answers
137
views
Dynamic Programming solution for problem "Number of 'B' characters in the first k characters of a fibonacci string"?
so I encountered this coding problem:
A Fibonacci string of A's and B's is constructed as follows:
F(0) = "A", F(1) = "B"
F(n) = F(n-1) + F(n-2) with n > 1
Given an integer n ...
0
votes
0
answers
40
views
How to identify overflow error with long?
I am trying to use memoization to identify when overflow occurs: But the error is not being thrown (the Runtimeexception) so is still just outputting negative values as the result
import java.util....
0
votes
0
answers
31
views
How to memoize a react function for older inputs?
I want this component to not calculate square callback on every click of button. Instead it should store previously calculated value and return. I understand that useMemo only caches the result of ...
0
votes
1
answer
41
views
Why component using context, always re-render?
I have a question with context
below this is my code
const { getValueFromKey, setValueToLocal, removeValueStorage } = useStorage<AuthStateValue>();
const [state, setState] = useState<...