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

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