Questions tagged [memoization]
An optimization technique where function calls are cached to avoid duplicate computations.
85 questions
5
votes
3
answers
957
views
LeetCode 678: Valid Parenthesis String, Recursion memoization to DP
How can the following recursion + memoization code be converted into a tabulation format dynamic programming solution?
The code is working, but I want to improve it.
The challenge I am facing is ...
4
votes
1
answer
117
views
Calculate optimal game upgrades, v2
This is the second iteration of the code I originally posted here: Calculate optimal game upgrades. Based on the feedback there, I chose to change the code to use a dynamic programming approach with ...
- 83
2
votes
1
answer
63
views
Further memoize context value in react?
This is a contrived example of a question that came up in code review the other day about memoizing context values in React. Let's say I have a hook which returns a memoized value of an expensive ...
- 155
7
votes
2
answers
1k
views
Convert 64-bit Gray code to integer
This algorithm encodes a 64 bit integer.
As input I have a 64 bit integer a, for example:
(a is a single 64 bit number,which I split in 8 bytes for readability) <...
- 173
1
vote
1
answer
598
views
Leetcode: 2327. Number of People Aware of a Secret
On day 1, one person discovers a secret.
You are given an integer delay, which means that each person will share the secret with a new person every day, starting from delay days after discovering the ...
- 21
2
votes
1
answer
194
views
k-dice Ways to get a target value
I'm trying to solve the following problem:
You have a k-dice.
A k-dice is a dice which have k-faces and each face have value written from 1 to k.
Eg. A 6-dice is the normal dice we use while playing ...
- 222
2
votes
2
answers
250
views
Generate the number of partitions of each integer
I've coded a program that calculates the number of partitions of n into at least two distinct parts, and is relatively quick too (about N^1.5 complexity). For input 30 000 it takes roughly 4 seconds. ...
- 21
0
votes
1
answer
92
views
Improving performance with a react modal where the component runs on every page
I have a simple cookie popup where the component technically runs on every page, giving the user the option to accept all or essential cookies. Once they accept an option, the popup no longer shows. ...
- 557
1
vote
1
answer
143
views
Python 3 weighted random choice function memoized version
I have written a function that randomly picks one element from a set with different probabilities for each element, anyway it takes a dictionary as argument, the keys of the dictionary are the choices ...
- 3,396
2
votes
1
answer
202
views
10
votes
1
answer
2k
views
Find all paths in a graph
My code does a DFS on the given graph and prints all possible paths for a given start and end node. My question is how can this be improved?
Can some form of memoization be used here? There are cases ...
- 165
3
votes
1
answer
319
views
Efficiently calculate value of Pascal's Triangle using memoization and recursion
So reading about functional programming, applications to dynamic programming, and learning Scala. I figured I would try it out with a popular example, Pascal's Triangle, tests against known values ...
- 133
6
votes
2
answers
1k
views
C++17 Recursive Fibonacci calculation with memoization
Compiler is g++ 4.2. I'm new to C++, but I've done a lot of data science, web scraping, and some socketing stuff in Python. This code generates the nth Fibonacci number, either with a naive ...
- 297
0
votes
3
answers
130
views
Advent of Code 2020, Day 10 in Ruby
I'm an amateur programmer making a career change into web development. I've found Advent of Code challenges are great way to sharpen my skills. I've cleaned up this solution for Day 10, 2020 as much ...
1
vote
1
answer
494
views
Optimizing solution of Sum of Pairs: Codewars in Python
I need help to optimize my code for huge lists with approx. 10000000 elements. Is there a way to improve my algorithm or should I try to build a new one using a completely different approach?
Task: ...
- 21