# Questions tagged [dynamic-programming]

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.

60 questions
1answer
72 views

### Maximize picks from a list when you can only choose 2 items from every 7 items [closed]

What would be an O(n) algorithm to maximize picks from a list when you can only choose 2 items from every 7 items. I've been thinking about this problem for a few days and I can't figure out an answer....
2answers
342 views

### Is 'call site' compiler generated auto code?

Is 'call site' some auto code generated by compiler - I come across this term frequently and it sounds like calling method is simply referred as 'call site' - which literally sounds fine but I believe ...
1answer
627 views

### Merging algorithm for overlapping intervals

I have been searching for an efficient algorithm to merge overlapping intervals on a dynamic array of intervals. For example, (start time, end time) wise, [(1, 2), (4, 8), (3, 10)] becomes [(1, 2)...
1answer
701 views

### find longest subsequence with sum less than or equal to k

I have a vector<int> num, I want to get the size of longest subarray with the sum less than or equal to k. My approach: O(n^2). Repeat for every element in the array. Can we do better?' ...
2answers
1k views

### Can the gold mine problem be solved using divide-and-conquer?

There's a well-known dynamic programming problem that goes by the name of the "gold mine." You have a n x n grid, each cell of which contains a certain value of coins. You begin at the bottom left ...
2answers
89 views

### Overlapping subproblems in immutable languages

Whenever I solve a problem with overlapping subproblems, I reach for memoization because it's so simple to implement. However, memoizing in an immutable language that doesn't have built-in support for ...
1answer
743 views

### Given an array of number, how to calculate to a target value

Chatting with a friend about a game we used to play, and thinking how to implement it in code. Here are the rules: Given a list of number e.g. {1,2,3,4} Try to use all the numbers from the list to ...
1answer
405 views

### Dynamic-programming matrix exercise [closed]

I'm practicing with dynamic programming and I'm trying to solve this exercise http://www.geeksforgeeks.org/collect-maximum-points-in-a-grid-using-two-traversals/ But I can't understand how to use ...
5answers
360 views

### My brute force solution is too slow, needed DP solution [closed]

Concise problem definition: given n and {a,b,c}; (1 ≤ n, a, b, c ≤ 4000); Constraint -> a*i + b*j + c*k==n (i,j,k>=0); Objective-> maximize(i,j,k) Examples: n=47 and a=7,b=5,c=8 -> ...
1answer
184 views

### Unable to Solve Dynamic Programming

I had an assignment on dynamic programming due last night, but I had to turn it in unfinished because i could not understand how to solve the last problem: The state wants to monitor traffic on a ...
2answers
368 views

### How to retrieve policy after Dynamic Programming?

I'm working on a simple resource allocation problem, that I'm solving using backward DP. The full code is at: https://codereview.stackexchange.com/questions/123641/allocating-a-resource It works fine,...
1answer
663 views

### Dynamic Programming: Shortest path with exactly k edges in a directed and weighted graph

I came across this problem of finding the shortest path with exactly k edges. After some searching, I found the code below. It uses a 3D DP. States are there for number of edges used, source vertex ...
1answer
450 views

### Dynamic Programming - Largest arrangement of bookcases

I'm trying to solve a problem, so I'm not looking for code, but for similar algorithms so I can solve it myself. I am given n bookcases each with a size amount of books inside. I am to move some of ...
1answer
258 views

### Finding all possible ways of inserting a pattern into a string

I've been thinking about this problem for a while, and I can only find a recursive solution but I'm feeling that there is a dynamic programming way to do it, I just can't figure it out. Is this a ...
2answers
664 views

### Find path of steepest descent along with path length in a matrix

Came across this problem -- You are given a grid with numbers that represent the elevation at a particular point. From each box in the grid you can go north, south, east, west - but only if the ...
1answer
869 views

### Maximizing Value and Volume, minimizing weight - Knapsack

Trying out a Knapsack variant where the rules are Any item you take must fit completely in the bag Usable metrics of the bag are length(l),width(w),height(h) and you can assume that if the products ...
1answer
719 views

### How to find a subset of size k such that the minimum distance between values is maximum

Suppose I have a sorted array which contains n integers. How do I find subset of size k such that the minimum distance between all pairs of integers in the subset is maximized, I mean they are at ...
0answers
129 views

### Select the sequence to minimize the cost

Lets say there is a delivery-boy who wants to distribute some food packets over N cities (1..N). We know the number Pi of packages that are to be delivered at city i. We know the distance between ...
1answer
1k views

### Grid walking explanation [closed]

There's a problem on hackerrank.com called Grid Walking. Here is its description: You are situated in an N dimensional grid at position (x1,x2,...,xN). The dimensions of the grid are (D1,D2,......
5answers
951 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 ...
3answers
436 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 ...
0answers
551 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 out ...
5answers
5k 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) ...
1answer
229 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 ...
3answers
5k 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: ...
3answers
299 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 ...
2answers
626 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 ...
2answers
1k 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 ...
1answer
108 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 ...
3answers
9k 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 ...
2answers
1k 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 ...
1answer
631 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 ...
1answer
77 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 ...
1answer
281 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 efficient ...
2answers
124 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 ...
1answer
2k 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 ...
1answer
452 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 ...
4answers
1k 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 ...
2answers
1k views

### Finding lowest cost path - dynamic

I have to write a dynamic algorithm for finding lowest cost path. So I have a point that I have to visit. I can jump only between points by distance - 5 I have an array of distance from 0-point for ...
1answer
487 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 ...
2answers
66 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)?
4answers
6k 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 ...
1answer
590 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 ...
1answer
593 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 ...
1answer
393 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 ...
3answers
901 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 ...
2answers
804 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 ...
3answers
3k 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 of ...
4answers
2k views

### C simple arrays and pointers question

So here's the confusion, let's say I declare an array of characters char name = "Sam"; and then I declare another array but this time using pointers char * name = "Sam"; What's the difference ...
3answers
2k 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 ...