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.
8
votes
3answers
310 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 ...
1
vote
0answers
78 views
Solving this dynamic programming problem
I am trying to solve this problem. I know that it involves dynamic programming, and that the recurrence relation is as follows:
For the minimum height starting with book "a",
MinHeight(a) = ...
1
vote
0answers
80 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 ...
0
votes
1answer
235 views
Can someone help me in creating a dynamic programming solution to this problem?
I have some function names which are assigned to some nodes. I have to decide which functions to move to other nodes to increase speed.
Why do I have to move the functions to other nodes? If ...
2
votes
1answer
200 views
Programming puzzle with constant selection
THE QUESTION:
There is an event where there are N contestants. There are three tasks in the event: A,B,C (say). Each participant takes part in the events in the listed order: i.e a contestant must ...
6
votes
4answers
257 views
Is there a correlation between the scale of the project and the strictness of the language?
Explaining the difference between strictness of languages and paradigms to a colleague of mine, I ended up asserting that:
Tolerant languages, such as dynamic and interpreted languages, are used ...
7
votes
3answers
395 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 ...
5
votes
2answers
217 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 ...
2
votes
2answers
267 views
Domino Solitaire Algorithm
Problem Statement -
Given a 2xN grid of numbers, the task is to find the most profitable tiling combination (each tile covers 2x1 cells; vertically or horizontally) covering all tiles.
I thought ...
-2
votes
4answers
670 views
C simple arrays and pointers question
So here's the confusion, let's say I declare an array of characters
char name[3] = "Sam";
and then I declare another array but this time using pointers
char * name = "Sam";
What's the ...
4
votes
3answers
595 views
Round Table - Minimum Cost Algorithm
Problem Link - http://www.iarcs.org.in/zco2013/index.php/problems/ROUNDTABLE
It's dinner time in Castle Camelot, and the fearsome Knights of the Round Table are clamouring for dessert. You, the ...
-2
votes
1answer
232 views
Grid Game Algorithm
Problem Link - http://www.iarcs.org.in/inoi/2009/zco2009/zco2009-1a.php
You have to find the path with the maximum weight, from the top-left cell to the bottom-right cell. It could've been solved ...
3
votes
2answers
183 views
Looking for a dynamic programming solution
Given a sequence of integers in range 1 to n. Each number can appear at most once. Let there be a symbol X in the sequence which means remove the minimum element from the list. There can be an ...
3
votes
3answers
640 views
Separating words in a string
How do I separate words in a string?
In the following I have a random sample of words in a string extracted from text file with over a million words.
Here's the string:
"intervene Pockets ...
1
vote
1answer
372 views
Minimizing use of paper
I've recently faced this problem in a dynamic programming curriculum, and I honestly have no idea about how to determine the appropriate state.
You're given N (1 <= N <= 70) paragraphs and M (1 ...
5
votes
2answers
1k 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 ...
3
votes
2answers
877 views
How to prove a Dynamic programming strategy will work for an algorithm?
How can I prove that a dynamic programming (dp) strategy for a problem will work or not? For greedy algorithms, we can prove by showing the sub problems exhibits matroid property.
Is there any such ...
2
votes
2answers
277 views
Help on a Dynamic Programming definition in Cormen
I am reading about Dynamic Programming from Cormen.
In the beginning of the chapter it says (relating to the term Dynamic Programming):
"Programming” in this context refers to a tabular method, ...
4
votes
4answers
408 views
Building a route creator
Ok, already up front, I'm going to tell you, that this is a bonus task for Data structure course I'm taking. That should take care of all the questions whether or not this is for a homework.
Route ...
3
votes
1answer
855 views
How to apply dynamic programming to optimization problems with 2 constraints
Suppose you have a collection of blocks, each with a certain height and a certain weight. For example:
Sample input:
(190, 190) (120, 40) (100, 10) (90,130) (70, 40) (60, 70) (30, 30) (10, 90)
...
8
votes
2answers
844 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 ...
6
votes
1answer
1k views
Is there a canonical book on dynamic programming?
At the moment in college I'm studying dynamic programming and I'm really interested in it. I want to go deeper and fully understand the topic so I can write good dynamic code.
Is there a book out ...
