All Questions
Tagged with dynamic-programming memoization
316 questions
0
votes
0
answers
38
views
Valid Parenthesis String, Recursion with 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 ...
0
votes
1
answer
98
views
Storing the recursive call result in a variable leads to incorrect calculation in a DP memoized solution
Just by using the commented code instead of making the recursive calls inside the max function, leads to incorrect result particularly with the following test case
int main() {
Solution obj = ...
- 409
1
vote
2
answers
146
views
What is the time complexity of the following algorithm and is there any optimization I can do?
Problem: Given an array that sums to 0, find the maximum number of partitions of it such that all of them sum up to 0 individually.
Example:
input: [-2, 4, -3, 5, -4]
output: 2 (which are [[5, -2, -3]...
- 5,791
0
votes
1
answer
71
views
Why is this DFS + Memoization solution for selecting indices in two arrays too slow while a similar approach is more efficient?
I was solving LeetCode problem 3290. Maximum Multiplication Score:
You are given an integer array a of size 4 and another integer array b of size at least 4.
You need to choose 4 indices i0, i1, i2, ...
- 2,052
0
votes
1
answer
53
views
3-D DP VS 2-D DP, can't seem to figure out why my code can't be memoized
class Solution {
public:
int countNeighborhoods(const vector<int>& houses) {
int neighborhoods = 0;
int m = houses.size();
for (int i = 0; i < m; i++) {
...
-3
votes
1
answer
105
views
Adding DP to 0/1 knapsack
Here are the two different ways of solving 0/1 knapsack using recursion.
#include<bits/stdc++.h>
using namespace std;
#define vi vector<int>
#define vb vector<bool>
long long solve1(...
- 3
3
votes
0
answers
58
views
Why does my recursive memoization function cause a 'Maximum Call Stack Exceeded' error in JavaScript?
While solving fabonocci problem using recursion and memoization in JavaScript, I got "Maximum Call Stack Exceeded" error when I try to run it with large inputs. To troubleshoot, I copied the ...
2
votes
3
answers
132
views
Is there a way initialize a matrix(2D array) with some default values(-1)
I was going through a dp problem, there I have to initialize the matrix with default(-1) values for memoized solution. And felt the need.
We can initialize the 1D array in java like this => Arrays....
- 64
0
votes
2
answers
309
views
Dynamic Programming - Minimum cost to fill given weight in a bag
We are given an array of positive weights cost where cost[i] represents the cost of filling i + 1 kg's of oranges in a bag (0-based indexing). We need to find the minimum cost to buy exactly w kg's of ...
- 45
0
votes
1
answer
84
views
How is it possible to memoize longest divisible subset using only the length (and end position)?
The goal is to find the largest divisible subset. A divisible subset is a subset s.t. for every pair of elements i, j, either i is divisible by j or j is divisible by i. The general approach to solve ...
- 9,643
2
votes
1
answer
69
views
Issue with Memoization in Recursive Function for Finding Combinations Summing to Target
I need to write the following function:
Write a function that takes in a target (int) and a list of ints. The function should return a list of any combination of elements that add up to the target, ...
- 158
0
votes
0
answers
133
views
Minimum Cost Path Recursion - Memoization
Given a square grid of size N, each cell of which contains integer cost which represents a cost to traverse through that cell, we need to find a path from top left cell to bottom right cell by which ...
1
vote
1
answer
1k
views
Why Is It Called Memoization?
Memoization is a programming technique where the results of expensive function calls are stored and reused, preventing redundant computations and improving performance.
Sample Memoization
import java....
- 6,928
0
votes
1
answer
274
views
LeetCode - Minimum Falling Path Sum - question on memoization
I am trying to solve this leetcode problem: https://leetcode.com/problems/minimum-falling-path-sum/description
Given an n x n array of integers matrix, return the minimum sum of any falling path ...
1
vote
0
answers
77
views
Why is this solution to Knight probability in chessboard wrong?
The problem statement from leetcode - https://leetcode.com/problems/knight-probability-in-chessboard/
Basically, knight starts from a given position and randomly picks 1 of 8 possible moves. It makes ...
- 23