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.
68 questions
-1
votes
4
answers
737
views
Leetcode: 2327. Number of People Aware of a Secret and Problem with programming skill in general
On day 1, one person discovers a secret.
You are given an integer delay, which means that each person will share the secret with a new person every day, starting from delay days after discovering the ...
- 15
1
vote
0
answers
146
views
Ideal Profits in companies in Perfect Binary Search tree
I'm trying to solve the following problems here:
In the X world, companies have a hierarchical structure to form a large binary tree network (can be assumed to be a perfect binary tree). Thus every ...
- 111
-1
votes
1
answer
96
views
Given n points in Cartesian 2D coords and only able to move directly from point to point how can you reach any point while minimising the longest jump
Let's say you're given n points e.g. A(1,2) B(4,2) C(3,1)
How could you reach any of the points from the orign while minimising the longest jump from point to point
For example: A: OA, B: OACB, C: OAC
...
- 11
-2
votes
2
answers
127
views
What to memoize in Dynamic programming questions?
How do you know what to memoize in top-down Dynamic Programming problems?
I understand it is to do with capturing the permutations of state. E.g. in the Fibonacci numbers question, it’s memoizing the ...
- 109
2
votes
2
answers
139
views
Optimal sequence of recipes
I assume the following is/reduces to a known problem, but I haven't been able to find it.
I have a sequence of recipes with associated costs. Each recipe converts a set of resources to another set of ...
- 290
0
votes
1
answer
204
views
How should I apply dynamic programming on the following problem
I have an array of events where events[i] = [startDay_i, endDay_i, value_i]. The ith event starts at startDay_i and ends at endDay_i, Attending the ith event, I will receive value_i. Also given an ...
- 23
1
vote
3
answers
478
views
Algorithm – Number of strings containing every string of a given set a strings
I have a given set S of strings, and a length l, and I am looking for the number of strings of length l that contains every string of S. A naive approach would be to generate every string of length l (...
- 141
1
vote
2
answers
1k
views
Calling recursive method in a loop - Backtracking
I'm confused about a matter that I've been unable to figure out. I'm doing some leetcode problems. In backtracking problems, sometimes we use loop within our recursive method to call the recursion but ...
- 127
1
vote
2
answers
280
views
design problem handling a dynamic object
I am writing an application for different geometrical types of fuel tanks.
I have a design problem that only at runtime I will receive the exact type of tank from the end user; and I don't know how ...
0
votes
1
answer
107
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....
- 13
0
votes
2
answers
1k
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 ...
- 1,450
1
vote
1
answer
1k
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)...
0
votes
1
answer
3k
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?'
...
- 109
2
votes
2
answers
2k
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 ...
- 129
3
votes
2
answers
145
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 ...
- 2,883
0
votes
1
answer
2k
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 ...
- 109
1
vote
1
answer
425
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 ...
- 19
5
votes
5
answers
456
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 -> max=...
- 169
-2
votes
1
answer
301
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 ...
4
votes
2
answers
416
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,...
- 149
1
vote
1
answer
917
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 ...
- 167
5
votes
1
answer
860
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 ...
- 187
7
votes
1
answer
319
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 ...
- 181
5
votes
3
answers
1k
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 ...
- 79
3
votes
1
answer
1k
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 ...
- 452
0
votes
1
answer
2k
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 ...
- 9
0
votes
1
answer
2k
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,...DN)...
- 109
5
votes
5
answers
1k
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 ...
- 3,263
7
votes
3
answers
533
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 ...
- 135
0
votes
0
answers
623
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 ...
- 3
3
votes
5
answers
6k
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)
Given ...
- 452
0
votes
1
answer
263
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 ...
- 1
7
votes
3
answers
9k
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:
...
- 79
9
votes
3
answers
518
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 ...
- 223
2
votes
2
answers
779
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 ...
- 105
5
votes
2
answers
3k
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 ...
- 205
1
vote
1
answer
150
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 now ...
- 119
4
votes
3
answers
16k
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 ...
- 49
4
votes
3
answers
3k
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 ...
- 141
0
votes
1
answer
824
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 will ...
- 3
4
votes
1
answer
86
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 ...
- 49
-1
votes
1
answer
316
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 ...
- 107
1
vote
2
answers
141
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 ...
- 21
4
votes
1
answer
3k
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 ...
- 199
-1
votes
1
answer
526
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 ...
- 101
5
votes
4
answers
3k
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 ...
- 161
1
vote
2
answers
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 ...
- 11
1
vote
1
answer
938
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 ...
user121210
0
votes
2
answers
87
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)?
19
votes
5
answers
10k
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 ...
- 305