New answers tagged dynamic-programming
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
