Questions tagged [dynamic-programming]
Dynamic programming is an algorithmic technique for efficiently solving problems with a recursive structure containing many overlapping subproblems.
289
questions
2
votes
0
answers
23
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,493
1
vote
1
answer
38
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
40
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 ...
- 273
2
votes
0
answers
52
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'.
...
- 311
2
votes
2
answers
208
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 ...
2
votes
2
answers
103
views
3
votes
3
answers
499
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 ...
2
votes
1
answer
205
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: [...
- 379
1
vote
1
answer
104
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 ...
- 247
4
votes
1
answer
534
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 ...
- 141
2
votes
1
answer
54
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 ...
- 21
0
votes
0
answers
76
views
Better Approach for the House Robbery Problem (LeetCode 198)?
The problem states that you have to rob the maximum money stashed in the houses but you cannot rob two adjacent houses. array[i] denotes the money in the (i)th house. I got the following code ...
- 57
1
vote
2
answers
158
views
Leetcode 377. Combination Sum IV Javascript Memoization attempt
Problem Statement
...
1
vote
1
answer
2k
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,003
0
votes
3
answers
294
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
...
3
votes
1
answer
162
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,493
5
votes
1
answer
66
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
72
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
98
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
74
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 ...
- 309
3
votes
1
answer
3k
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
69
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
0
votes
0
answers
63
views
Efficiently calculate value of Pascal's Triangle using memoization and recursion(updated)
Follow up to Efficiently calculate value of Pascal's Triangle using memoization and recursion
Based on feedback given by jvwh in the answers
...
- 133
3
votes
1
answer
140
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
0
answers
110
views
LeetCode: Delete and Earn C#
https://leetcode.com/problems/delete-and-earn/
Given an array nums of integers, you can perform operations on the
array.
In each operation, you pick any nums[i] and delete it to earn nums[i]
points. ...
- 5,249
1
vote
0
answers
52
views
LeetCode: range sum query mutable c#
https://leetcode.com/problems/range-sum-query-mutable/
I am trying to solve this question using dynamic programming.
I guess the guys in leetcode want to limit us to use segment tree or one of the ...
- 5,249
-1
votes
1
answer
87
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 ...
4
votes
1
answer
141
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
68
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
1
vote
0
answers
34
views
Divide a set into subset with some constraints
Note - I am not sure whether this question belongs to stackoverflow or CSE stackexchange or here
Problem:
Given a list Lconsisting of not necessarily unique non-...
- 161
3
votes
0
answers
98
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
225
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,249
1
vote
1
answer
591
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
0
votes
1
answer
197
views
Generate unique string permutations recursively
🧩 Objective
Write a recursive method for generating all permutations of an input string. Return them as a set.
See: Recursive String Permutations - Interview Cake
🔎 Questions
1: How does the ...
- 239
9
votes
1
answer
1k
views
LeetCode on Longest Palindromic Substring in Python
This is a programming question from LeetCode:
Given a string s, return the longest palindromic substring in s.
Example 1:
Input: s = "babad" Output: "bab" Note: "aba" is ...
user5235
2
votes
1
answer
45
views
Why below recursive DP solution is so slow? (Leetcode Q# 123 - Best Time to Buy and Sell Stock III)
This is regarding leetcode Question# 123. I have solved the question (code below) but the solution is showing "Your runtime beats 5.89 % of cpp submissions."? Is there any additional ...
- 121
3
votes
0
answers
333
views
Split money into every possible combination of coin denominations
Background and objective of the code
Based on this Dev.to challenge, I wrote the Python code below (TIO link also available).
The task was to return the least number of coins in a given denomination ...
- 401
4
votes
1
answer
114
views
C++ Dynamic Array Class Testing
I'm creating a basic Dynamic Array class in C++, and I'd like to know if there are any bugs/memory leaks I haven't noticed yet.
dyn_arr.h :
...
2
votes
1
answer
65
views
Find sequence to a target number using restricted set of primitive operations
Given an integer 𝑛, compute the minimum number of operations(+1, x2, x3) needed
to obtain the number 𝑛 starting from the number 1.
I did this using this code:
...
- 23
2
votes
2
answers
116
views
Knapsack performance issue
I'm solving a knapsack problem here. It works, but gives time limit exceeds on a certain test case.
Problem statement
There are N
items, numbered 1,2,…,N. For each i (1≤i≤N), Item i has a weight of ...
- 167
0
votes
1
answer
312
views
LeetCode 1320: Minimum Distance to Type a Word Using Two Fingers II
I'm posting my Python code for LeetCode's 1320. If you have time and would like to review, please do so.
Problem
You have a keyboard layout as shown above in the XY plane, where each English ...
- 3,369
1
vote
1
answer
101
views
LeetCode 1320: Minimum Distance to Type a Word Using Two Fingers I
I'm posting my C++ code for LeetCode's 1320. If you have time and would like to review, please do so. Thank you!
Problem
You have a keyboard layout as shown above in the XY plane, where each English ...
- 3,369
-1
votes
1
answer
235
views
LeetCode 375: Guess Number Higher or Lower II
I'm posting my C++ code for LeetCode's Guess Number Higher or Lower II. If you have time and would like to review, please do so.
Problem
We are playing the Guess Game. The game is as follows:
I pick ...
- 3,369
2
votes
1
answer
364
views
How can I use the State monad effectively in Haskell?
I have written a simple fibonacci function in Haskell that uses the State monad to save solutions to overlapping sub-problems. Now despite the function working I am not really happy with the solution, ...
- 495
1
vote
1
answer
525
views
Maximum subset sum with no adjacent elements
Write a function that takes an array of integers (Both Positive and negative) and return the maximum sum of non adjacent elements. Note that even if all values are negative, I don't have an option to ...
- 185
1
vote
2
answers
142
views
Recursive brute-force approach to maximum points you can obtain from cards
I came across this question on Leetcode. The question description is as follows:
There are several cards arranged in a row, and each card has an associated number of points.
The points are given in ...
- 113
2
votes
2
answers
72
views
(Java) Read .txt and organize activities for hours / minutes
Doubts in logic to generate the output file according to the example
I need that even if he reaches the total_min <720 condition he continues to travel the lines. 720 is the total number of minutes ...
- 123
1
vote
1
answer
66
views
Matrix problem, the path that is the flattest
So in this problem I am given an NxN matrix, in which each value of the matrix represents an altitude. I need to find the best path from the top-left corner to the bottom-right one, my moves being ...
2
votes
1
answer
120
views
LeetCode: Trapping Rain Water DP C#
Please review for performance and C# style.
I already solved this question in 1 way.
LeetCode: trapping rain water C#
I tried also the dynamic programming approch
https://leetcode.com/problems/...
- 5,249
2
votes
2
answers
288
views
C# - Reapply the manipulation of JS Object in .Net Core
IMPORTANT:
I made another version with some improvements: Version 2
Since some months ago I disagree with the native/code methods to manipulate dynamic or ...
- 227