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.
6
votes
4answers
207 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
341 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
187 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
197 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
583 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
477 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
202 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
171 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
470 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
366 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 ...
4
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
3answers
664 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
260 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
400 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
647 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
732 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
3answers
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 ...
