# Questions tagged [dynamic-programming]

Dynamic programming is an algorithmic technique for efficiently solving problems with a recursive structure containing many overlapping subproblems.

294 questions
Filter by
Sorted by
Tagged with
1 vote
71 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 "...
• 113
1 vote
99 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
55 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 ...
51 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 &...
73 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
130 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 ...
197 views

### Longest Palindromic Substring | Python Code Giving TLE

Problem Statement Given a string s , return the longest palindromic substring in s. Constraints ...
• 138
74 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,675
1 vote
49 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 ...
50 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 ...
• 293
95 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'. ...
895 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 ...
114 views

...
617 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 ...
565 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: [...
• 389
1 vote
166 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 ...
• 319
1k 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
95 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
92 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
244 views

### Leetcode 377. Combination Sum IV Javascript Memoization attempt

Problem Statement ...
1 vote
3k 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
364 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 ...
176 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,675
124 views

### K Inverse Pairs Array - Brute Force

For an integer array nums, an inverse pair is a pair of integers [i, j] where ...
• 195
86 views

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
114 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 ...
85 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 ...
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
95 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
183 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
1 vote
61 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,337
153 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 ...
148 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
71 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
126 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
109 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[]...
244 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,337
1 vote
807 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
224 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
2k 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 ... 62 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
519 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 ...
• 458
129 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 : ...
75 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: ...
151 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
360 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,477
1 vote
123 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,477
256 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,477
543 views