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
votes
0answers
77 views

Project Euler problem 31 - tail recursive algorithm? [closed]

The Problem's details are in the following link : Project Euler Problem 31 The following code illustrates a simple recursive solution object Problem_31 extends App { def combinations(list: ...
0
votes
0answers
59 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
112 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
227 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
101 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
39 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
100 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
848 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
164 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
274 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
237 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
431 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
323 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
398 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
852 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
693 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
351 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
224 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
1k 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
379 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
315 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
420 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
1k 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 ...