Questions tagged [dynamic-programming]
Dynamic programming is an algorithmic technique for efficiently solving problems with a recursive structure containing many overlapping subproblems.
297 questions
5votes
2answers
176views
LeetCode Number 416: Partition Equal Subset Sum
Problem: MLE I am confused as to why the LeetCode judge reports Memory Limit Exceeded when my solution looks close to the editorial solution. I not too familiar with ...
5votes
3answers
962views
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 ...
4votes
1answer
117views
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
1vote
1answer
106views
Finding the number of distinct decompositions a number has using only repdigits
This is a problem from a previous semester that I am trying to upsolve. I am trying to solve a problem involving the total number of ways of decomposing a number using only repdigits. A repdigit is a ...
2votes
1answer
50views
Optimal Extraction of Longest Sorted Sequence from Individually Sorted Bucket Arrays Without Repetitions
Consider a bucket array containing sorted and/or empty buckets, and the goal is to extract the longest possible sequence in sorted order, under the following conditions: Only one element in each ...
- 121
6votes
1answer
347views
Codeforces: D2. Counting Is Fun (Hard Version)
The code works okay for the following problem. Problem An array 𝑏 of 𝑚 non-negative integers is said to be good if all the elements of 𝑏 can be made equal to 0 using the following operation some (...
- 244
1vote
0answers
44views
Collecting inputs from a list of file names or stdin if there is no input files
In my program, I want to either read from a file or stdin depending on the arguments. I did this function to collect input: ...
- 111
5votes
2answers
953views
C++ - Secretary Problem using dynamic programming
I tried using dynamic programming to get a solution to the Secretary Problem. It seems to me it's working with with expected result. I really didn't want to use ...
- 153
1vote
3answers
133views
Another ATMs cash-out (denomination) algorithm in Java
Related to this question and this answer, I would like to have a second review from you on a modified version. The problem I tried to solve Some kind of "Minimum count of numbers required from ...
2votes
5answers
299views
Sum of bitwise XOR of each subarray weighted by length
here is the problem statement You are given an array a of length n consisting of non-negative integers. You have to calculate the value of \$\sum_{l=1}^n \sum_{r=l}^n f(l,r)\cdot (r - l + 1)\$ where \...
1vote
1answer
598views
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
4votes
2answers
131views
Find largest sum not involving consecutive values
There is a question to basically find the largest sum in an array, such that no two elements are chosen adjacent to each other. The concept is to recursively calculate the sum, while considering and ...
2votes
1answer
194views
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
1vote
1answer
163views
Longest (more or less) ideal subsequence
An ideal subsequence is a subsequence of a string, where the distance between adjacent characters in the subsequence is bounded by a maximum, i.e. \$\lvert c[i] - c[i\pm 1] \rvert \leq k\$ Example: ...
- 11
2votes
2answers
166views
Making my DP algorithm faster - longest palindromic substring
The following code is my solution to a LeetCode question - find the longest palindromic substring. My code is 100% correct, it passed once but it took too long, and in most of the reruns I hit a "...
- 123
