Linked Questions

0 votes
0 answers

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, ...
nicku's user avatar
  • 143
28 votes
4 answers

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{ ...
Raphael's user avatar
  • 71.9k
18 votes
6 answers

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. ...
Computernerd's user avatar
14 votes
2 answers

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 ...
Anonymous's user avatar
  • 141
5 votes
4 answers

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 ...
Blanco's user avatar
  • 613
4 votes
2 answers

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 ...
Arat254's user avatar
  • 227
1 vote
1 answer

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!".
Yurii's user avatar
  • 103
1 vote
1 answer

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 ...
sgmm's user avatar
  • 121
1 vote
1 answer

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 ...
Rnet's user avatar
  • 111
6 votes
1 answer

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 ...
Arat254's user avatar
  • 227
-1 votes
1 answer

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 ...
Ivan's user avatar
  • 273
1 vote
1 answer

For dynamic programming problems, how do we know the subproblems will share subproblems?

So, a common reasoning to use dynamic programming as the website ( mentions is that, we use dynamic programming when: ...
user123215321631443's user avatar
3 votes
0 answers

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 ...
Thomas's user avatar
  • 31
-1 votes
1 answer

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: ...
harun_a's user avatar
  • 135
1 vote
2 answers

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 ...
Toothless's user avatar