New answers tagged dynamic-programming
1
I'm going to assume by "doesn't work" you mean "gives the wrong answer".
In dynamic programming, every cell in the table is supposed to represent a solution to a subproblem. In the case of edit distance, the subproblem is
Let dp[i][j] be the distance between word1.substring(i) and word2.substring(j)
But in your code, the statement of ...
1
Standard dynamic programming approaches are likely not going to work for this problem, because the extra "this or that but not both" constraints destroy the overlapping subproblems property. So let's break out the sledgehammer.
You can easily encode this as a 0-1 integer linear programming problem and use an off-the-shelf solver. For the given ...
0
The difficulty of your problem heavily depends on "constraint".
For example if $n=3k$, $\text{size}=[\underbrace{3,3,3,...}_{k\text{ times}}]$, and the constraint is that the sum of the numbers each group must be equal, then your problem is strongly NP-hard since it is exactly $3$-partition.
The same problem with groups of size $2$ is polynomial.
...
1
The issue is that you might not enter the second "if" when the current sum is smaller than nums[i].
Imagine, e.g., that at the beginning of the iteration you have currentSum=-5, max=100, nums[i]=10.
At the end of the iteration you have currentSum=5 and max=100, yet the desired state is currentSum=10, max=100.
A corresponding instance where your ...
0
If $W \ge n \cdot P$ you can add all elements in the knapsack.
Otherwise $W < n \cdot P$ in which case any algorithm with complexity $O(n W)$ will also have complexity $O(n \cdot (nP)) = O(n^2P)$. In particular the pseudo-polynomial dynamic programming solution described in Wikipedia works in $O(n W)$.
1
Let $DP[i]$ be the number of distinct valid campaigns whose last marketing email is the $i$-th email, $i$ from $1$ to $n$. As an extension, let $DP[0]=1$, which is the number of distinct valid campaigns without marketing emails.
For all $i\le k+1$, it is clear that the only valid campaign whose last marketing email is the $i$-th email is the campaign that ...
1
A similar problem, named "Black Hole", appears as one of the problems of 2019 Russian Olympiad of schoolchildren in computer science.
The problem asks for a program that interacts with a jury program simulating probe sensors and determines the radiation level of each black hole. The sensor mounted on the probe can answer the following queries: ...
1
Let $T$ be your tree, and root it in an arbitrary vertex $r$.
Given a vertex $v$, let $T_v$ denote the subtree of $T$ rooted at $v$.
For simplicity, let $f(0, v) = 0$.
For $i \ge 0$, define $D[v,i]$ as the minimum cost needed to cover the subtree rooted at $v$ if all the nodes at distance smaller than $i$ from $v$ are always considered as covered. ...
1
In this answer it's assumed there's at most 1 lie in the sense that if you ask the same question twice and get the same answer twice, you know for sure that it's not a lie.
Using the observation in Nir Shahar's answer, an algorithm can be constructed that performs at most $\lceil\log_2{n}\rceil + 2\lceil\sqrt{\lceil\log_2n\rceil}\rceil + 1$ (or slightly less)...
2
Your formula is wrong (I would like to see where exactly this formula appears in the course, it is not in the gif you linked).
The correct formula is the following:
Let $n$ be your amount. Let minCoins be an array of $n+1$ elements indexed from $0$ to $n$, where minCoins$[i]$ is the minimum amount of coins needed to give change for the amount $i$. Let $c_1, ...
4
For $i=1,\dots,N$, and $r \in \{S,R,B\}$
define $OPT[i,r]$ as
the maximum profit that can be obtained by robbing a suitable subset of the first $i$ houses with the following constraints:
If $x=S$ (as in Skip) then house $i$ must not be robbed.
If $x=R$ then house $i$ must be Robbed while house $i+1$ will not be robbed (to avoid a case distinction later we ...
0
The easiest way to tackle this problem is to first solve it with a
non-deterministic solution, then use dynamic programming to change it into a
deterministic one.
The main difficulty here is that the problem is so specific that the
specifics hide a simple solution that can be applied to a much wider class of
problems.
So I will first généralise the problem....
Top 50 recent answers are included
