Linked Questions

28
votes
4answers
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{ ...
19
votes
6answers
16k 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. ...
14
votes
2answers
15k 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 ...
5
votes
4answers
598 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 ...
1
vote
1answer
1k 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 ...
4
votes
2answers
512 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 ...
1
vote
1answer
997 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!".
1
vote
1answer
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 ...
-1
votes
1answer
1k 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 ...
6
votes
1answer
357 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 ...
3
votes
0answers
765 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 ...
1
vote
1answer
273 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: ...
-1
votes
1answer
532 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: ...