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.
1
vote
2answers
108 views
Finding common prefixes for a set of strings
I am trying to find common prefixes for a sorted set of strings. i.e. if the following strings are given:
AB123456
AB123457
ABCDEFGH
ABCDEFGX1
ABCDEFGY
XXXX
then my function should return three ...
0
votes
1answer
52 views
Number of sequences when no adjacent items can be the same
I came across this one problem,
There is a particular sequence only uses the numbers 1, 2, 3, 4 and no two adjacent numbers are the same.
Write a program that given n1 1s, n2 2s, n3 3s, n4 4s ...
3
votes
1answer
45 views
How to diversify an optimal solution set?
If given a list of players, their salaries, and their projections, one can easily find the top 'n' projected teams (where a team is a combination of players), such that every team is under the salary ...
-1
votes
1answer
205 views
Competitive Programming [closed]
I think this may just be one of the most frequently asked questions by a novice (like me) on this site. Please pardon me for that. My question is I wish to get better at solving the harder problems of ...
-1
votes
1answer
275 views
optimise my solution
I just solve this but want know more efficient way to do matrix multiplication
M :
------
1 1 0
0 0 5
3 2 0
f[n] = M^n
I have implemented using Exponentiation_by_squaring
Is there more ...
1
vote
2answers
70 views
Need to organize words based on their components, any other way aside from brute force?
I'm not sure if this process has a name.
I have some words (about 9,000). They are in Japanese, but I'll try to explain this using English words. I want to categorize the words by the components (in ...
1
vote
0answers
103 views
Dynamic programming in Bin packing
Problem: Given a list L of objects of possible sizes from set S={1,2,4,8} and unlimited supply of bins of sizes 16 each and we have to use minimum possible numbers of bins to pack all objects of L.
I ...
-1
votes
1answer
128 views
How to solve linear recurrences involving two functions?
Actually I came across a question in Dynamic Programming where we need to find the number of ways to tile a 2 X N area with tiles of given dimensions..
Here is the problem statement
Now after a bit ...
5
votes
4answers
256 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 ...
0
votes
2answers
118 views
finding lowest cost path - dynamic
I have to write a dynamic algorithm for finding lowest cost path. So I have a points that I have to visit. I can jump only between points by distance - 5 I have an array of distance from 0-point for ...
0
votes
0answers
42 views
Algorithm for HIghest Local Alignment Score with a specific character match between two subsequences
I'm writing a code that identifies the highest-scoring local alignment between a substring X' of X and a substring Y' of Y that has at least one column in which a C from X' is aligned to a W from Y'.
...
1
vote
1answer
109 views
Memoization Memory
Memoization is definitely a powerful technique.
But Dynamic Programming is slightly better IMO, since it does not involve the memory strain (in a recursive program, the parameters occupy memory and ...
0
votes
2answers
57 views
Is array dependence on previous terms considered recursive?
For example, take the case of Fibonacci number to calculate nth number you require n-1 and n-2 term.
If I do it with bottom up approach, is it recursion as f(n) depends on f(n-1)?
12
votes
4answers
1k 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
172 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
284 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
243 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 ...
7
votes
3answers
454 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
342 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
527 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
927 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
739 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
441 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
235 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
2k 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
380 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 ...
6
votes
2answers
2k 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
1k 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
334 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
423 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
2k 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
1k 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
2k 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 ...
