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.

learn more… | top users | synonyms

1
vote
5answers
263 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 ...
6
votes
3answers
401 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 ...
0
votes
0answers
54 views

scrabble solving with maximum score

I was asked a question You are given a list of characters, a score associated with each character and a dictionary of valid words ( say normal English dictionary ). you have to form a word ...
3
votes
4answers
749 views

Robot in a grid

This was recently asked to someone I know. A robot has to move in a grid which is in the form of a matrix. It can go to A(i,j)--> A(i+j,j) (Down) A(i,j)--> A(i,i+j) (Right) ...
0
votes
1answer
116 views

dynamic programming with memoization

I’ve a problem with a programming exercise. I hope you can help me. In this exercise I need to find out what the maximum profit is of taking pictures from several items in a park. For taking pictures ...
4
votes
2answers
382 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: ...
6
votes
3answers
184 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 ...
2
votes
2answers
240 views

Dynamic Programming Problem - To find smallest integer number 'x' which contains only digits 1's and 0's such that x mod n = 0

To design an algorithm that will output the smallest integer number 'x' which contains only digits 1's and 0's such that x mod n = 0 and x > 0..... For example: 2 divides 10 3 divides 111 4 ...
3
votes
2answers
385 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 ...
1
vote
1answer
88 views

find the minimum number of sets

Let's explain my question with example I have some integer sets for example S1 = {2,3} S2 = {2, 5} S3 = {4, 5} S4 = {4} S5 = {5} And I have sample set Ssample with 4 elements {2, 3, 4, 5}. So ...
2
votes
3answers
4k views

Efficient algorithm to count number of substrings divisible by 3

Given a string of decimal digits, I have to find the number of all substrings divisible by 3 in the range L to R [both inclusive], where L & R are index[1-based] of the specified string string ...
1
vote
2answers
298 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
241 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
53 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 ...
0
votes
1answer
417 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
277 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
78 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 ...
2
votes
0answers
211 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
158 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
414 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
253 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 ...
1
vote
1answer
145 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)?
13
votes
4answers
2k 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 ...
3
votes
0answers
212 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
304 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
249 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
537 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
474 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
770 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
1k 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
854 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
565 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 ...
4
votes
2answers
246 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
2answers
3k 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
384 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 ...
7
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
2k 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 ...
3
votes
2answers
360 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
439 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
2k 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 ...