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
3 votes
3 answers
178 views

Max contiguous slice in Ruby

I need to compute the max contiguous slice in an array. I wrote this function, but I am not sure if it is correct or I am missing edge cases. I ran several cases. ...
aarti's user avatar
  • 913
2 votes
1 answer
10k views

Implementation of Sequence Alignment in C++

Below is my implementation of the dynamic programming solution to the sequence alignment problem in C++11: ...
doge's user avatar
  • 23
14 votes
5 answers
3k views

DP example for "Power of Two" in Python

I'm not familiar with Python but want to provide a code snippet for an SO question about Dynamic Programming. The snippet should show the bottom-up approach of DP. The function ...
sschmeck's user avatar
  • 486
11 votes
1 answer
2k views

House-coloring optimization challenge

I have an interview coming up in the next few weeks, and I'm choosing to be interviewed in Python. I began programming in Python (it was about four years ago), so the syntax is natural to me, but I ...
Mark Miller's user avatar
10 votes
2 answers
300 views

Undo format when format disappears

I was posed a question as follows: Given a sentence like "John is a bad man", lets say all the formatting disappears and you are left with one string "johnisabadman". Given a dictionary of words, ...
sc_ray's user avatar
  • 1,213
6 votes
2 answers
5k views

Longest Increasing Subsequence

I am learning dynamic programming and I have written down some code for longest increasing subsequence. I would like to know if there is any case or any area of improvement in the terms of ...
Gaurav Gupta's user avatar
8 votes
2 answers
2k views

Counting Increasing Subsequences of size K recursive

The original description of the problem can be found here, its input here and its expected output here. The problem: Given a integer sequence a1 ... an (-10000 \$\leq\$ ai \$\leq\$ 10000). Where ...
user avatar
4 votes
4 answers
12k views

Find the minimum number of coins

I'm trying to learn dynamic programming and the most popular one is to find the minimum number of coins for the change. I come up with this but I just want to improve this code which I think it could ...
toy's user avatar
  • 831
6 votes
1 answer
117 views

Optimal way to annihilate a list by removing items from the ends

I'm stuck with a contest problem. Description: What is the minimum number of moves to annihilate an int array where the possible moves are: Remove both the first and last elements if they are equal ...
john's user avatar
  • 63
4 votes
2 answers
6k views

Finding all the subsets in an array of integers that sum to a given target

Problem Statement: Given an Array if ints, Find out all the subsets in the Array that sum to a given target value. Example: If the input array is: ...
Anirudh's user avatar
  • 872
5 votes
1 answer
2k views

Minimum number of coins - (dynamic programming solution - topdown approach)

This is a problem from topcoder tutorials Given a list of N coins, their values (V1, V2, ... , VN), and the total sum S. Find the minimum number of coins the sum of which is S (we can use as many ...
lightning_missile's user avatar
8 votes
1 answer
167 views

Reading, processing and counting an array setting limits

Last weekend my teacher asked me to create code to solve a problem: Giving a dynamic array, we want to pass the array elements from a file. The first number in the file N gives us the array length. ...
Nikos KLon's user avatar
2 votes
1 answer
2k views

Solving the rod-cutting problem using dynamic programming

I've written what I believe is a valid dynamic programming solution to a variation of the rod cutting problem. In this problem, the goal is to make as few cuts as possible on a rod of length n. I ...
jesse34212's user avatar
1 vote
0 answers
2k views

DP algorithm to find minimum average wait for customer-serving system

Below is the code to find the minimum average waiting time for customers at a store. I want improve the time complexity of the code. As an overview of the logic, I start from ...
Meena Chaudhary's user avatar
4 votes
1 answer
945 views

Optimizing a dynamic programming solution for "Oil Well"

I'm trying to solve the Oil Well problem on Hackerrank using dynamic programming and it works. However, it times out for some of the test cases. I wanted to know how this program can be improved so ...
ssh's user avatar
  • 95
1 vote
1 answer
2k views

Coin problem through brute force

I have some code that will brute force solve the following problem: Given a set of x coins and a target sum to reach, what is the fewest number of coins required to reach that target? The code so ...
spyr03's user avatar
  • 3,032
10 votes
1 answer
3k views

Project Euler #14 -- longest Collatz sequence

I was reading this question and realized that I didn't know Python well enough to critique the algorithm. So I wrote a Java solution instead, which is inappropriate for that question. Since there's ...
Brythan's user avatar
  • 6,984
3 votes
1 answer
2k views

Calculate possible balances in piggy-bank by weight

I have solved Piggy-Bank problem on SPOJ using dynamic programming. The question asks you to get the minimum value that is possible with given weight (\$w\$) and one or more coins (\$n\$) with given ...
Hasil Sharma's user avatar
5 votes
1 answer
1k views

Word break problem with dynamic programming

This is the original question. I have implemented it in both ways. If I enter the word "icecream", should I output "ice" "cream" and also "icecream", or just "ice" and "cream"? Is this a good ...
Gilad's user avatar
  • 5,311
2 votes
1 answer
228 views

Memoization for calculating minimal traversal distance within a positive matrix

The code below is for calculating the minimal traversing distance from the top left point of the matrix to the bottom right point of the matrix. GitHub Here is the core functionality. Please note ...
Kevin's user avatar
  • 143
4 votes
1 answer
590 views

Google CodeJam Round D APAC Test

Problem A: Vincenzo decides to make cube IV but only has the budget to make a square maze. Its a perfect maze, every room is in the form of a square and there are 4 doors (1 on each side of the ...
user2761431's user avatar
3 votes
1 answer
1k views

Dynamic Programming for printing additive numbers up to digits n

Edit: I am hoping to get some review / make sure I am understanding dynamic programming correctly. I am trying to print out all additive numbers up to digits n using dynamic programming. Additive ...
user3898238's user avatar
3 votes
2 answers
879 views

Longest Common Subsequence and Longest Subsequence Palindrome

The following code computes: The longest common subsequence between two strings, where a subsequence of a sequence does not have to consist of contiguous elements of the sequence. The longest ...
Millie Smith's user avatar
8 votes
3 answers
474 views

Handling shared state among a lot of elements in Angular

I am working on a project in Angular where I have a number of similar data objects. When you click on anyone of them it's state and amount of data shown will change. All of the objects start in the ...
EasilyBaffled's user avatar
3 votes
2 answers
5k views

Longest collatz sequence using dynamic programming

I am trying to solve longest collatz sequence problem under 1000000 with the below code. Can anyone suggest a faster way to approach this problem? I was thinking of dynamic programming, but I'm ...
user avatar
4 votes
3 answers
3k views

Project Euler 81 (minimum path sum through a matrix)

Problem Statement: In the 5 by 5 matrix below, 131 673 234 103 18 201 96 342 965 150 630 803 746 422 111 537 699 497 121 956 805 732 524 37 331 ...
mleyfman's user avatar
  • 5,170
11 votes
3 answers
2k views

Substitution cipher algorithm performance boost

This algorithm is meant to read a string of numbers on an input, a naive substitution cipher code (A = 1, B = 2, ..., Z = 26) and output the number of ways the code could be interpreted (e.g. 25114 ...
mirgee's user avatar
  • 305
1 vote
2 answers
101 views

Making operations more dynamic

I am trying to build something that will allow us to configure "custom" validation for each customer. So if a customer wants to see a value contain a specific char, be specific length, or equal ...
DeadlyChambers's user avatar
2 votes
2 answers
467 views

Calculating the number of prime numbers to solve the puzzle

How can the following program execution time improved? I have used dynamic programming in both "recursive" as well as "prime" function, but I'm not getting the efficient execution time. There is a ...
Torrtuga's user avatar
12 votes
5 answers
7k views

Dynamic programming with Fibonacci

I have written the following code using a dynamic programming technique. Can I use ArrayList here? Please let me know if I can improve this code. ...
VIckyb's user avatar
  • 665
4 votes
1 answer
233 views

NGON (many polygons) on SPOJ

I am trying to solve NGON problem. I am using bottom up dynamic programming here. Recurrence function is: $$\begin{array}{rl} f(a,b) &= f(a-1,b) + f(a-1,b-1)\,a_i +\frac{f(a-1,b-2)\,a_i(a_i-1)...
Naman's user avatar
  • 183
11 votes
1 answer
197 views

Loading Data Warehouse with Dynamic SQL

For a data warehousing project I ran into the following: Custom fields that users can create, modify and delete, that should be loaded into the data warehouse as they are when the ETL happens. On ...
Tristan's user avatar
  • 211
2 votes
1 answer
832 views

Determine if subset in int array adds up to a given input integer

Given a set of non-negative integers, and a value sum, determine if there is a subset of the given set with sum equal to given sum. On similar lines, Partition problem is to determine whether a given ...
JavaDeveloper's user avatar
4 votes
2 answers
697 views

The Three-machine proportionate flow shop problem with unequal machine

As part of an Academic project I wrote the following code, according to the algorithm (verbal). When I checked the rest of the article I notice that the efficiency should be \$O(n^2)\$ and I wrote \$...
user3446659's user avatar
4 votes
1 answer
496 views

Dynamic programming with Project Euler #18

I just wanted to get an opinion on my dynamic-programming Haskell implementation of the solution to Project Euler problem 18. The Problem: By starting at the top of the triangle below and moving ...
sakekasi's user avatar
5 votes
2 answers
5k views

Optimizing O(m n) solution for longest common subsequence challenge

Given two strings string X of length x1 and string Y of length ...
swapedoc's user avatar
  • 457
7 votes
1 answer
553 views

Three-machine proportionate flow shop problem with unequal machine

As part of an academic project I wrote a code about dynamic programming that solves the "Three-machine proportionate flow shop problem with unequal machine". In flow shop scheduling it is ...
user3446659's user avatar
11 votes
3 answers
1k views

Optimizing "Herd Sums" problem using dynamic programming

I'm trying to solve a practice problem and all is well except for the last 2 inputs my solution is too slow. Just one loop is slowing it down I think. Herd Sums Execution Time Limit: 2 seconds ...
jantristanmilan's user avatar
7 votes
2 answers
4k views

Finding alternating sequence in a list of numbers

Please be brutal and treat this as me coding this up for an interview. A sequence of numbers is called a zig-zag sequence if the differences between successive numbers strictly alternate between ...
bazang's user avatar
  • 2,236
8 votes
1 answer
2k views

Assembly line scheduling

This is solution to the assembly line problem. Here is complete description, which is too big and verbose to re-describe. I apologize for the inconvenience of the hyperlink. Note: I do understand ...
JavaDeveloper's user avatar
1 vote
1 answer
1k views

Knapsack 01 solution

Solution to bounded knapsack 01 problem. Once again comprehensive description is difficult in this space, refer here. Looking for code review. optimizations and best practices. ...
JavaDeveloper's user avatar
4 votes
2 answers
338 views

Returning all the LIS of given array of int

I have this assignment where I'm supposed to code an algorithm for finding the quantity of Longest Increasing Subsequences from an array of (different) integers and print them all. I developed one ...
JeremieG's user avatar
1 vote
1 answer
1k views

MaxSum sub matrix within a matrix

Code review for best practices, optimizations, code cleanup etc. Also requesting verification of the complexity: O(row*row*col). ...
JavaDeveloper's user avatar
6 votes
2 answers
1k views

Box-stacking problem in C++

I have tried to write code of Box stacking problem (mentioned here) in C++ . Kindly give me some views on what mistakes I might have made and how I can improve. It is running for the two inputs I have ...
tariq zafar's user avatar
2 votes
1 answer
2k views

Project Euler #82 - path sum: three ways

Project Euler problem 82 asks: Here's my solution: ...
Eugene Yarmash's user avatar
3 votes
1 answer
4k views

Jump game in Java

Looking for code review, suggestions for improvement, best practices etc. The problem definiton is Jump Game Given an array start from the first element and reach the last by jumping. The ...
JavaDeveloper's user avatar
4 votes
2 answers
5k views

Project Euler #15 -- count possible lattice paths

I'm not a C programmer, just wanted to make a fast solution to the problem. Starting in the top left corner of a 2×2 grid, and only being able to move to the right and down, there are exactly 6 ...
Eugene Yarmash's user avatar
58 votes
3 answers
69k views

Dynamic programming knapsack solution

I wrote a solution to the Knapsack problem in Python, using a bottom-up dynamic programming algorithm. It correctly computes the optimal value, given a list of items with values and weights, and a ...
voithos's user avatar
  • 862
7 votes
4 answers
8k views

Python implementation of the longest increasing subsequence

Prompted by this question on Stack Overflow, I wrote an implementation in Python of the longest increasing subsequence problem. In a nutshell, the problem is: given a sequence of numbers, remove the ...
gcbenison's user avatar
  • 347

1 2 3 4 5
6