Questions tagged [dynamic-programming]
Dynamic programming builds solutions from solutions to simpler subproblems. It's closely allied to recursion, but dynamic programming algorithms are formulated as iteration usually over a very regular datastructure.
68 questions
19
votes
5
answers
10k
views
How do you identify a problem as being suitable for dynamic programming?
I have been reading up on dynamic programming lately. Would like to hear from someone who started from scratch and now is pretty good at identifying and solving DP problems. I am struggling in ...
- 305
9
votes
3
answers
525
views
number of strings, when each character must occur even times
I've been bashing my skull at this problem for some time now, and its really starting to frustrate me. The problem is:
I have a set of characters, A, B, C, and D. I have to tell in how many ways a ...
- 223
9
votes
2
answers
3k
views
How to get better at solving Dynamic programming problems
I recently came across this question: "You are given a boolean expression consisting of a string of the symbols 'true', 'false', 'and', 'or', and 'xor'. Count the number of ways to parenthesize the ...
- 93
9
votes
2
answers
6k
views
How is the "Pizza picking problem" solved using dynamic programming techniques?
Winkler's pizza picking problem:
A circular pizza pie of n slices, where slice i has area S_i i.e, the area is different for each pie piece.
Eaters Alice and Bob take turns picking slices, but it is ...
- 91
8
votes
3
answers
1k
views
Longest subsequence without string
Does there exist a dynamic programming algorithm to find the longest subsequence in a string X that does not contain Y as substring? Just that this problem seems so similar to other DP string ...
- 81
7
votes
3
answers
534
views
Picking m number in the best possible time
Imagine we want to pick m numbers from n numbers so that the difference of the maximum and minimum of the m numbers be minimum, for example if
m = 4
n =6
numbers: 10 12 10 7 5 22
The ...
- 135
7
votes
3
answers
9k
views
Number of strings containing a specific substring
I've seen numerous questions (and answers) concerning the number of binary strings (e.g "10010" containing some binary substring (e.g "00"). I'd like to know if there is a way to generalize this:
...
- 79
7
votes
1
answer
319
views
Finding all possible ways of inserting a pattern into a string
I've been thinking about this problem for a while, and I can only find a recursive solution but I'm feeling that there is a dynamic programming way to do it, I just can't figure it out. Is this a ...
- 181
6
votes
1
answer
686
views
Help/suggestions for Parallel assembly line scheduling (Dynamic programming)
I am working on a problem similar to the assembly line scheduling by dynamic programming.The issue is that unlike the classic problem where we have predefined stations now I only have information ...
user109405
5
votes
3
answers
1k
views
Find path of steepest descent along with path length in a matrix
Came across this problem --
You are given a grid with numbers that represent the elevation at a particular point. From each box in the grid you can go north, south, east, west - but only if the ...
- 79
5
votes
5
answers
1k
views
Are mocks in unit tests dangerous in dynamic languages?
I've started relying heavily on a mocking framework in php for my unit tests.
My concern is that with a dynamic language, there is no way of enforcing a return type. When mocking, you have to ensure ...
- 3,263
5
votes
4
answers
3k
views
The optimal recipe problem
Suppose I have a list of Ingredients In My Fridge which are going off soon, and a list of Recipes which use up various Ingredients. (Some of which I don't currently have.)
Is there an algorithm which ...
- 161
5
votes
5
answers
458
views
My brute force solution is too slow, needed DP solution [closed]
Concise problem definition:
given n and {a,b,c};
(1 ≤ n, a, b, c ≤ 4000);
Constraint -> a*i + b*j + c*k==n (i,j,k>=0);
Objective-> maximize(i,j,k)
Examples:
n=47 and a=7,b=5,c=8 -> max=...
- 169
5
votes
2
answers
3k
views
Looking for a DP algorithm for a specific packing problem
I have the following problem to solve:
Given a ferry with length d and a list of n cars conataining their length we must load the cars on the ferry in an order in which they appear in the list on 2 ...
- 205
5
votes
2
answers
1k
views
Training Camp Algorithm
Problem Statement -
The task is to find the most profitable contiguous segment of tests, given a sequence of test scores, with being allowed to drop any k tests from a chosen range.
The problem ...
- 449