A message from our CEO about the future of Stack Overflow and Stack Exchange. Read now.

# Tag Info

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 ...

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 ...

0

Your algorithm is pseudo-polynomial, since it is polynomial in the parameter $\operatorname{max\_sum}$ that is inputted using $\log(\operatorname{max\_sum})$ bits. However we will show that your problem is NP-complete, therefore your algorithm, although in practice exponential, is a reasonable choice. Let's define the Subset Sum Problem (SSP): given $a_1, ... 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$...

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 ...

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 ...

3

A conditional lower bound based on max-plus convolution can be shown: Fix $n = 3$. If a $\mathcal{O}(k^{2 - \epsilon})$ algorithm to this problem (with fixed $n$) exists, then MAXCONV could be solved in $\mathcal{O}(n^{2 - \epsilon})$. Max-plus convolution is a reasonable hardness assumption, as it is a much-studied problem for which no $\mathcal{O}(n^{2 - \... 2 Suppose that the candidates are$x_1,\ldots,x_n$and the target is$T$. I'm assuming all candidates are positive. If$T < 0$then there are no solutions. If$T = 0$then the only solution is the empty solution. Otherwise, there are two kinds of solutions:$x_1$together with a solution for$T - x_1$using all candidates. A solution for$T\$ using the ...

Top 50 recent answers are included