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
741
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
147
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
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
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
1
vote
3
answers
480
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
-2
votes
2
answers
128
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
-1
votes
1
answer
98
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
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
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
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
2
votes
2
answers
5k
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 ...
- 129
1
vote
2
answers
285
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 ...
7
votes
3
answers
534
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
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