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
-1votes
4answers
532views
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
1vote
0answers
133views
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
-1votes
1answer
81views
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 ...
-2votes
2answers
119views
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
2votes
2answers
117views
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
0votes
1answer
190views
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
1vote
3answers
451views
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
1vote
2answers
1kviews
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
1vote
2answers
253views
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 ...
0votes
1answer
91views
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
0votes
2answers
996views
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
1vote
1answer
1kviews
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)...
0votes
1answer
3kviews
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?' ...
2votes
2answers
2kviews
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
3votes
2answers
133views
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,863
