Questions tagged [dynamic-programming]
Dynamic programming is an algorithmic technique for efficiently solving problems with a recursive structure containing many overlapping subproblems.
297 questions
3
votes
1
answer
140
views
Calculate optimal game upgrades, v3
This is the third iteration of the code from Calculate optimal game upgrades, v2 and Calculate optimal game upgrades. I'm looking for suggestions to further optimize this code. A brief summary of the ...
- 125
5
votes
2
answers
229
views
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 ...
- 53
5
votes
3
answers
1k
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
161
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 ...
- 125
1
vote
1
answer
137
views
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 ...
- 59
2
votes
1
answer
71
views
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
6
votes
1
answer
420
views
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
5
votes
2
answers
992
views
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
1
vote
3
answers
179
views
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 ...
- 1,000
2
votes
5
answers
358
views
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 \...
1
vote
1
answer
632
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
4
votes
2
answers
178
views
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 ...
- 43
2
votes
1
answer
236
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
1
vote
1
answer
203
views
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
2
votes
2
answers
182
views
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
1
vote
2
answers
1k
views
Leetcode 55. Jump Game solution
I was working on Jump Game problem on leetcode
Question
You are given an integer array nums. You are initially positioned at the array's first index, and each element in the array represents your ...
- 189
1
vote
1
answer
2k
views
Re-order table columns in HTML dynamically with Javascript
I've a table in HTML looks like this:
Subjects
n1
n2
n3
subject1
10
0
0
subject2
0
5
20
...
- 593
3
votes
1
answer
136
views
Segmentation of list to minimize the largest sum
I have written the following code for diving a list 'seq' into 'k' segments such that the maximum sum of each segment is minimized. I have used dynamic programming to solve this problem. But my class &...
2
votes
1
answer
118
views
Find all non-crossing tuples which has the same content with a given tableau
Let T be a semistandard Young tableau of rectangular shape. For example,
[[1,2,4],[3,5,6]]
is such a tableau, where [1,2,4] and [3,5,6] are columns. All non-...
- 183
2
votes
1
answer
498
views
make html table in sync with javascript array
I have an array of users containing user name with their rules on my practice project
I have generated a table in HTML from that array in JS, So I can
change the ...
- 593
3
votes
1
answer
295
views
Longest Palindromic Substring | Python Code Giving TLE
Problem Statement
Given a string s , return the longest palindromic substring in s.
Constraints
...
- 138
2
votes
1
answer
145
views
Coin partitions
I am looking to obtain the partitions of coins that sum to a target amount
So I tried search online, but every single website loves to use this problem to show the benefits of dynamic programming. ...
- 5,795
1
vote
1
answer
103
views
Longest Increasing Subsequence of Rectangles
Background
I was looking at some programming Olympiads the other day, and I found this ACM-ICPC Ukraine 2013 pdf.
The part I am working on is Problem D, which consist of finding out how many rectangle ...
- 111
5
votes
1
answer
85
views
RodCutting and learning Dynamic Programming
I tried to learn dynamic programming going from recursion to memoized version with the RodCutting problem: Returns the best obtainable price for a rod of length n and price[] as prices of different ...
- 333
2
votes
0
answers
152
views
Bellman-Ford algorithm implementation
I have used an adjacency list to represent the graph.
This implementation is based on the procedure given in the book 'Introduction to Algorithms'.
...
- 371
2
votes
2
answers
2k
views
HackerRank: Sam and substrings | How can dynamic programming be used in my code?
Given a number as a string, no leading zeros, determine the sum of all integer values of substrings of the string.
Given an integer as a string, sum all of its substrings cast as integers. As the ...
- 147
1
vote
2
answers
167
views
4
votes
5
answers
878
views
Find maximum value of recursively-defined "fusc" function
I've been trying this question from SPOJ, which asks for the user to enter a number n, and they will receive a maximum fusc value that lies in between 0 to ...
user244000
3
votes
1
answer
867
views
Divide array into three disjoint sets with equal sum
Problem definition : Array partition problem
Given an array of positive integers, divide it into three disjoint subsets having equal sum. These disjoint sets cover the complete array.
Example
Input: [...
- 399
1
vote
1
answer
283
views
Target Sum array using Dynamic Programming
I'm learning Dynamic Programming and trying to solve this Target Sum array problem. I've to find an array of integers that sums to a given target sum using the integers of given input array. I've used ...
- 429
3
votes
1
answer
3k
views
Recursive solution of ordered Coin Combinations II (CSES)
Question Link
Consider a money system consisting of n coins. Each coin has a positive integer value. Your task is to calculate the number of distinct ordered ways you can produce a money sum x using ...
- 131
2
votes
1
answer
144
views
Find ALL duplicate subtrees. using recursion
This is just a practice exercise, I'm trying to understand dynamic programming as deeply as I can. I solved this using recursion, though I am not sure if it will always work. If anyone could tell me a ...
- 121
1
vote
2
answers
354
views
Leetcode 377. Combination Sum IV Javascript Memoization attempt
Problem Statement
...
1
vote
1
answer
7k
views
Patch a JSON object using dynamic / ExpandoObject with System.Text.Json
Background
Recently, I was making some updates to an "older" library that would handle PATCH-style modifications to an object that is persisted in a JSON format on our document-storage ...
- 1,023
0
votes
3
answers
525
views
Calculate sum of a substring
I try to solve some old Codeforces questions. The problem is;
Petya once wrote a sad love song and shared it to Vasya. The song is a
string consisting of lowercase English letters. Vasya made up q
...
- 177
3
votes
1
answer
256
views
Killing a Hydra - Overengineered
Background
This question is inspired by the question: Killing a hydra, and my response therein. I will restate the problem at hand in full so that this question is fully self contained
You can only ...
- 5,795
5
votes
1
answer
238
views
K Inverse Pairs Array - Brute Force
For an integer array nums, an inverse pair is a pair of integers [i, j] where ...
- 195
3
votes
1
answer
133
views
Haskell implementation of Needleman-Wunsch
The code below is a Haskell implementation of Needleman-Wunsch algorithm for sequence alignment (and string edit distance). It's an experiment in trying to closely imitate the dynamic programming ...
- 33
1
vote
2
answers
172
views
I want reduce the time complexity for this ladder problem to find the minimum ladders required
I was trying to attempt below given challenge. I tried multiple ways to solve the problem but none of them were good enough to pass the time limit. Please advise if you have any idea to improve on ...
- 13
4
votes
2
answers
119
views
Unique Paths II, dynamic programming problem, O(n^2) time, O(n^2) space
This is based on this leetcode question. I get the correct answer, but I know it could be much, much cleaner. I also know there is supposed to be an O(n) space solution, but I'm not sure how to ...
- 319
3
votes
1
answer
4k
views
Count the number of distinct subarrays
I want to determine the number of distinct subarrays that can form having at most a given number of odd elements. Two subarrays are distinct if they differ at even one position. The subarray is a ...
- 31
2
votes
1
answer
159
views
Haskell Dynamic Programming on a Tree
Here is my shot at Homework 8 of CIS-194 (from Spring '13). The problem is about a hierarchy of employees at a company (a tree), each node being of type Employee, ...
- 125
3
votes
1
answer
348
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
0
votes
1
answer
415
views
Grid Dynamic Programming
atcoder.jp Problem Statement:
There is a grid with H horizontal rows and W vertical columns. Let (i,j) denote the square at the ...
- 13
4
votes
1
answer
191
views
Searching for an idiomatic Rust implementation of Minimum Edit Distance (LeetCode #72)
I am solving LeetCode Dynamic Programming challenges (this one is #72, at https://leetcode.com/problems/edit-distance).
Here below, I've implemented a Rust solution for the minimum edit distance ...
- 143
0
votes
1
answer
99
views
Find a sum using just two different digits
The problem statement was pretty easy and I was able to run half of the test cases, but some of the test cases in the end gave me the error of memory limit reached. What can I do here to improve the ...
- 13
3
votes
2
answers
390
views
Divide a set into subset with some constraints
Problem:
Given a list L consisting of not necessarily unique non-negative integers, find the minimum number of subset with maximum sum ...
- 191
3
votes
0
answers
159
views
C++ - Longest Common Subsequence
Link to the Problem
Here is my code to compute the length of the longest common subsequence of two integer arrays arr[] and brr[]...
- 31
3
votes
0
answers
320
views
LeetCode: Stone Game C#
https://leetcode.com/problems/stone-game/
Alex and Lee play a game with piles of stones. There are an even
number of piles arranged in a row, and each pile has a positive
integer number of stones ...
- 5,443
1
vote
1
answer
1k
views
Code A Primitive Calculator ( x3,x2,+1) Using Dynamic programming [closed]
Question -You are given a primitive calculator that can perform the following three operations with the current number 𝑥: multiply 𝑥 by 2, multiply 𝑥 by 3, or add 1 to 𝑥. Your goal is given ...
- 21