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.

Filter by
Sorted by
Tagged with
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 ...
mfaani's user avatar
  • 33.9k
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):...
stack underflow's user avatar
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 ...
ABC123's user avatar
  • 21
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 ...
Hari Prasad's user avatar
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'...
Florent M.'s user avatar
  • 1,251
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 ...
GaNk1n1t's user avatar
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 ...
Gokhan Celikkaya's user avatar
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 ...
vikash tiwary's user avatar
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 ...
Saeed Mansoori's user avatar
-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. ...
Paurab Bhattacharjee's user avatar
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 ...
Kaustubh's user avatar
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 ...
Isaac Corbrey's user avatar
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 ...
driver's user avatar
  • 212
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 ...
Niels Koop's user avatar
-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, ...
N00B_141's user avatar
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 ...
Non_CS_Dude's user avatar
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. ...
curiousengineer's user avatar
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, ...
meez's user avatar
  • 4,033
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): # ...
RXEsquivel's user avatar
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 ...
Damien Martin's user avatar
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 ...
Tanya Sharma's user avatar
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 ...
Cristian Scalingi's user avatar
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 ...
Muhammad Umer Farooq's user avatar
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 ...
John Doe's user avatar
  • 2,807
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==...
Venkata Jayanarayan's user avatar
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 ...
Nandeesh Bhatrai's user avatar
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 ...
feois's user avatar
  • 21
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 ...
user25470's user avatar
  • 585
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, ...
curiousengineer's user avatar
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 ...
curiousengineer's user avatar
-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 ...
X-_-FARZA_ D-_-X's user avatar
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 ...
curiousengineer's user avatar
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 ...
user avatar
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 ...
chocalaca's user avatar
  • 354
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 ...
Federico's user avatar
  • 582
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 @...
Mighty's user avatar
  • 53
-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] = ...
THN's user avatar
  • 3,421
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 ...
myol's user avatar
  • 9,060
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 ...
Warren Buffet's user avatar
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'...
isosubjectix's user avatar
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(*...
Imaginary's user avatar
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 ...
Seth Lutske's user avatar
  • 9,484
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 ...
jbk's user avatar
  • 1,930
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....
Никита Белотелов's user avatar
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 ...
Apoorv Gupta's user avatar
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()]); } // ...
Anias Wagner's user avatar
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 ...
dvmbCateDoinAStroll's user avatar
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....
a2s4342's user avatar
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 ...
Priyanshu's user avatar
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<...
Trung Phan's user avatar

1
2 3 4 5
30