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
- Bountied 0
- Unanswered
- Frequent
- Score
- Trending
- Week
- Month
- Unanswered (my tags)
-1
votes
4
answers
706
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 ...
1
vote
0
answers
139
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 ...
-1
votes
1
answer
88
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
...
-2
votes
2
answers
120
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 ...
2
votes
2
answers
125
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 ...
0
votes
1
answer
195
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 ...
1
vote
3
answers
465
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 (...
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 ...
1
vote
2
answers
270
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
96
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....
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
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?'
...
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 ...
3
votes
2
answers
137
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 ...