Linked Questions
15 questions linked to/from What is dynamic programming about?
0
votes
0
answers
30
views
Defining dynamic programming [duplicate]
Could we say that Dynamic programming is nothing but recursion + Memoization?
Although the formal definition of dynamic programming is that the problem should have an optimal substructure property, ...
- 143
28
votes
4
answers
2k
views
How to find a superstar in linear time?
Consider directed graphs. We call a node $v$ superstar if and only if no other node can be reached from it, but all other nodes have an edge to $v$. Formally:
$\qquad \displaystyle $v$ \text{ ...
- 71.9k
18
votes
6
answers
17k
views
How is Dynamic programming different from Brute force
I was reading up on Dynamic Programming when I came across the following quote
A dynamic programming algorithm will examine all possible ways to
solve the problem and will pick the best solution. ...
- 639
14
votes
2
answers
16k
views
When can I use dynamic programming to reduce the time complexity of my recursive algorithm?
Dynamic programming can reduce the time needed to perform a recursive algorithm. I know that dynamic programming can help reduce the time complexity of algorithms. Are the general conditions such that ...
- 141
5
votes
4
answers
747
views
Is there a formal definition of sub-instances or sub-problems?
A decision problem is denoted as a language $L \subseteq \Sigma^{*}$.
For every instance $x \in \Sigma^{*}$, we say $x$ is a yes-instance if $x \in L$ and a no-instance if $x \not\in L$.
For some ...
- 613
4
votes
2
answers
701
views
Thought process to solve tree based Dynamic Programming problems
I am having a very hard time understanding tree based DP problems. I am fairly comfortable with array based DP problems but I cannot come up with the correct thought process for tree based problems ...
- 227
1
vote
1
answer
1k
views
What is the difference between dynamic programming and a mere caching?
I mean why should we use such epic buzzword when you can say: "cache your results!".
- 103
1
vote
1
answer
2k
views
How can you determine what set of boxes will maximize nesting?
I'm trying to find a dynamic solution to the nesting boxes problem.
You're basically given a set of "boxes" which all have different dimensions. The goal is to find the maximum set of boxes that can ...
- 121
1
vote
1
answer
1k
views
Understanding tables in Dynamic programming
I came across this problem that asks you to implement a regular expression matcher with support for '.' and '*', where
'.' Matches any single character.
'*' Matches zero or more of the preceding ...
- 111
6
votes
1
answer
460
views
Struggling to understand the thought process required to come up with some recurrences for Dynamic Programming problems
I was doing a few dynamic programming problems and I am struggling to understand the thought process required to come up with recurrences.
The first problem I solved was longest palindromic substring ...
- 227
-1
votes
1
answer
2k
views
How to balance parentheses/brackets in a string with minimum cost?
Given a word composed of opening and closing parentheses and brackets, we can do two operations:
Rotate a parentheses or bracket. That is, you can replace ( for ), ) for (, [ for ] and ] for [. This ...
- 273
1
vote
1
answer
581
views
For dynamic programming problems, how do we know the subproblems will share subproblems?
So, a common reasoning to use dynamic programming as the website (https://www.tutorialspoint.com/data_structures_algorithms/dynamic_programming.htm) mentions is that, we use dynamic programming when:
...
3
votes
0
answers
806
views
How to "convert" a top-down solution to a bottom-up algorithm? [duplicate]
When I'm working on a algorithm problem, I can usually find a top-down solution that works with recursion.
Then for optimization purpose I try to do a bottom-up approach (dynamic programming) to ...
- 31
-1
votes
1
answer
727
views
Check if a string can be split into two subsequences
Given a string S of length N, a string A of length M, a string B of length O such that N >= M + O. Check if the string S can be split into two subsequences X and Y such that A = X and B = Y.
Example: ...
- 135
1
vote
2
answers
48
views
Dynamic Programming- Calculating visit in a weighted matrix
I found this question on a forum chat on and while looking at it I thought I can solve it using recursion,
A group of friends is split into cells in a room in a random
arrangement of m X n cell ...
- 69