Skip to main content

Questions tagged [dynamic-programming]

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

Filter by
Sorted by
Tagged with
2 votes
1 answer
32 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 ...
4 votes
5 answers
801 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 ...
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 ...
6 votes
1 answer
320 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 (...
1 vote
0 answers
36 views

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: ...
5 votes
2 answers
927 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 ...
2 votes
5 answers
280 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
0 answers
69 views

3ph 2l inverter simulation with SPWM

Here is a code for a simple model of three phase two level inverter with constant DC voltage source and three phase RL load. ...
1 vote
3 answers
113 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 vote
0 answers
166 views

Wrapping an ExpandoObject within a SafeExpandoObject

I've written code to deserialize a JSON into an ExpandoObject. The only problem with the ExpandoObject is that if you try to access a member which doesn't exist, it ...
1 vote
1 answer
580 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 ...
4 votes
2 answers
116 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 ...
1 vote
1 answer
277 views

Project Euler # 21 amicable numbers Python

Let \$d(n)\$ be defined as the sum of proper divisors of \$n\$ (numbers less than \$n\$ which divide evenly into \$n\$). If \$d(a) = b\$ and \$d(b) = a\$, where \$a ≠ b\$, then \$a\$ and \$b\$ are an ...
1 vote
1 answer
291 views

Simple Factor Class

I have a class which lazily factors numbers. It provides the user with these methods: getFactors returns a ...
2 votes
1 answer
183 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 ...
0 votes
1 answer
155 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: ...
8 votes
3 answers
294 views

Splitting a rectangular chocolate bar

I'm having trouble with my school homework. I have a chocolate bar that consists of either black, white or black&white (mixed) squares. I'm supposed to divide it in two groups, one that has only ...
0 votes
1 answer
366 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 ...
1 vote
2 answers
156 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 "...
1 vote
1 answer
1k 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 ...
6 votes
1 answer
729 views

Multiple 0-1 knapsack

I have a problem were the time in minutes of N songs are given and I have to write the maximum number of time in K CDs. Input description The first input line consists of two positive integers N e K (...
3 votes
1 answer
106 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
84 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-...
3 votes
1 answer
262 views

Longest Palindromic Substring | Python Code Giving TLE

Problem Statement Given a string s , return the longest palindromic substring in s. Constraints ...
4 votes
2 answers
3k views

Optimal matrix chain multiplication in Java

Preliminaries Given two matrices $$ A = \begin{pmatrix} a_{11} & a_{12} & \dots & a_{1q} \\ a_{21} & a_{22} & \dots & a_{2q} \\ \vdots & \vdots & \ddots & \vdots \\ ...
2 votes
1 answer
466 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 ...
2 votes
1 answer
118 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. ...
2 votes
1 answer
411 views

An iterator returning all possible solutions to n-queen problem in Java - follow-up

(See the initial iteration.) Now I have slightly improved performance of the iterator. Whenever we have set a queen at a particular board cell, the previous iteration sacrifices \$\mathcal{O}(n)\$ ...
1 vote
1 answer
75 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 ...
1 vote
1 answer
6k 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 ...
5 votes
1 answer
64 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 ...
2 votes
0 answers
137 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'. ...
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 ...
1 vote
2 answers
138 views

finding whether two string are anagrams of each other [closed]

...
3 votes
1 answer
832 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: [...
1 vote
2 answers
342 views

Leetcode 377. Combination Sum IV Javascript Memoization attempt

Problem Statement ...
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 ...
1 vote
1 answer
235 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 ...
2 votes
1 answer
122 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 ...
0 votes
3 answers
467 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
222 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 votes
1 answer
220 views

K Inverse Pairs Array - Brute Force

For an integer array nums, an inverse pair is a pair of integers [i, j] where ...
3 votes
1 answer
113 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 ...
8 votes
5 answers
2k views

Repeatedly partitioning an array equally as far as possible

I solved HackerRank Nikita and the Game. The implementation is correct as program passes all test cases. Nikita just came up with a new array game. The rules are as follows: Initially, ...
1 vote
2 answers
121 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 ...
4 votes
3 answers
13k views

Calculating the sum of array elements to the left and right

I am using C++ to code the following logic: An Array is given we have to traverse the array such that sum of array elements to its left must be equal to sum of elements to its right. BTW this is ...
3 votes
2 answers
1k views

Counting the number of ways to decode a string

I am working on problem where I need to decode a string: A message containing letters from A-Z is being encoded to numbers using the following mapping: 'A' -> 1 'B' -> 2 ... ...
4 votes
2 answers
99 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 ...
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 ...
2 votes
1 answer
129 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, ...

1
2 3 4 5 6