# Tag Info

5

Hint #1: Hint #2:

3

There is a $\mathcal{O}(nk)$ DP approach. Call an edge covered if we select a vertex next to it. Root the tree at an arbitrary vertex $r$. Define $DP[i][b][t]$ as the maximum number of edges in the subtree of node $i$ that can be covered by selecting at most $t$ nodes from the subtree. If $b = 0$ we are not allowed to select node $i$, and if $b = 1$ we must ...

3

I don't know if this helps, but I also struggled a great deal with DP problems on trees, and what helped for me was considering some simpler problems first, and really do a bunch of exercises of this type. It also really helps to program them in (e.g.) Python so that you get some hands-on experience. So, perhaps it is better to start with a simpler tree ...

1

I didn't try reading the source code there, but here is one way to achieve $O(2^{3n/2})$ edit distance computations (but NOT $O^*(2^{3n/2})$ time overall). Let's define $D(a, b)$ as the Levenshtein edit distance between two strings $a$ and $b$ -- that is, the minimum number of single-character insertions, deletions or substitutions required to turn one into ...

1

Question 1 The reason why its O(1) space and not O(n) comes down to top down vs bottom up. Let us first consider the array based problem - min path sum. If you do it top down you will need O(n^2) space. Remember that when you do top down/memoization, all the state results need to be stored - its essentially just recursion with caching. However when you ...

1

The function $$f:\mathbb{N}\rightarrow\{0, 1\}:f(k) = \begin{cases} 1; &\text{if there is a solution of size k,}\\ 0; &\text{otherwise} \end{cases}$$ is monoton, since if there is no solution of size $k$ then there is no solution of size $k+1$. That means we can binary search the value of $k$ in the interval $[1, |B|]$, and output the greatest $... 1 A simple solution is to use the state$dp(n,2,n)$. Let$dp(i,0,j)$be the maximum number of edges we can get by using$\leq j$nodes in the subtree rooted at node$i$, with node$i$itself not being in the vertex cover. Let$dp(i,1,j)$be the same, except node$i\$ is included in the vertex cover. The transition itself is not obvious, but it can be done ...

1

Here is a way to solve the problem of longest valid parentheses by dynamic programming as you had hoped. Or almost. For simplicity, a string is called valid if it consists of well-formed opening and closing parentheses. The critical observation is that a string is valid if it is the empty string, a concatenation of two valid strings or "(" followed by a ...

Only top voted, non community-wiki answers of a minimum length are eligible