40
Knapsack problem is $\sf{NP\text{-}complete}$ when the numbers are given as binary numbers. In this case, the dynamic programming will take exponentially many steps (in the size of the input, i.e. the number of bits in the input) to finish $\dagger$.
On the other hand, if the numbers in the input are given in unary, the dynamic programming will work in ...
35
The principle of dynamic programming is to think top-down (i.e recursively) but solve bottom up. So a good strategy for designing a DP is to formulate the problem recursively and generate sub-problems that way.
33
The main confusion lies in the difference between "size" and "value".
"Polynomial Time" implies polynomial w.r.t the size of input.
"Pseudopolynomial Time" implies polynomial w.r.t the value of the input. It can be shown (below) that this is equivalent to being exponential w.r.t the size of the input.
In other words: Let $N_{size}$ represent the size of ...
27
To use the bottom up method you need to be able to efficiently determine what the "bottom" is, which usually means you need a heavily constrained problem space. If you know what the lowest level calculations are going to be and the dependency order going upward, it makes sense to iteratively do them in the proper order and store those results. Factorials, ...
26
Dynamic programming gives you a way to think about algorithm design. This is often very helpful.
Memoization and bottom-up methods give you a rule/method for turning recurrence relations into code. Memoization is a relatively simple idea, but the best ideas often are!
Dynamic programming gives you a structured way to think about the running time of your ...
17
A dynamic programming algorithm will examine all possible ways to solve the problem and will pick the best solution.
This statement is just plain wrong.
Dynamic programming recurrences do (often) consider all possible ways to split the given problem instance into smaller instances according to some scheme. However, it will not combine all solutions to all ...
15
There are plenty of other examples of dynamic programming algorithms that don't fit your pattern at all.
The longest increasing subsequence problem requires only a one-dimensional table.
There are several natural dynamic programming algorithms whose tables require three or even more dimensions. For example: Find the maximum-area white rectangle in a bitmap....
14
The different dimensions are independent. What you can do is compute, for each dimension j, how many different walks there are in just that dimension which take $t$ steps. Let us call that number $W(j,t)$. From your question, you already know how to compute these numbers with dynamic programming.
Now, it's easy to count the number of walks that take $t_i$ ...
14
It's not a technical term with a precise meaning, it is just the English word "naive". In a computer science context, the word usually means something like "one of the things you would think of first, but without realizing a less obvious but important fact".
For instance, if one knows the definition of Fibonacci numbers is $\mathrm{Fib}(n) = \mathrm{Fib}(n-...
11
When we say polynomial or exponential, we mean polynomial or exponential in some variable.
$nW$ is polynomial in $n$ and $W$. However, we usually consider the running time of an algorithm as a function of the size of the input.
This is where the argument about $\log W$ comes in. Ignoring the values of the items for the moment (and considering only their ...
11
The longest path problem does have optimal substructure, and this can be used to improve the trivial $O(n!)$ algorithm to an $\tilde{O}(2^n)$ algorithm. First we have to generalize the problem:
Generalized longest path: Given a graph $G=(V,E)$, two vertices $s,t \in V$, and a set of vertices $A \subseteq V \setminus \{s,t\}$, find the longest path in $G$ ...
10
There is no (one) formal definition of "optimal substructure" (or the Bellman optimality criterion) so you can not possibly hope to (formally) prove you have it.
You should do the following:
Set up your (candidate) dynamic programming recurrence.
Prove it correct by induction.
Formulate the (iterative, memoizing) algorithm following the recurrence.
9
The basic idea is: Try out all cut positions as first choice, solve the respective parts recursively, add the cost and choose the minimum.
In formula:
$\qquad \displaystyle \operatorname{mino}(s, C) =
\begin{cases}
|s| &, |C| = 1 \\
|s| + \min_{c \in C} \left[ \begin{align}&\operatorname{mino}(s_{1,c}, \{c' \in C \mid c' < c\})\ \\ +\...
9
Actually, there is nothing special in the name "dynamic programming"; the technique itself is just about smartly unwinding recursion. See this question and look at @Jeffe answer, in which is reported that Belman choose that name to be intentionally distracting.
9
Very nice question!
You are twice right:
Propagating the number of items in the knapsack does not lead to optimal solutions.
One solution consists of adding a third dimension. This is rather simple but it is necessary to take some facts into account when doing so. Note however that it is not the only alternative
In the following, I am assuming that you ...
9
Dynamic Programming is clever as it reuses computation, while brute force doesn't. Suppose to solve, f(6), you need to solve 2 sub-problems which both call f(3). The brute force method will calculate f(3) twice thereby wasting effort while dynamic programming will call it once, save the result in case future computations need to use it. In many problems, ...
9
I am using terminology and notations from Earley's paper. It is possible that the description you read is different.
It seems frequent that general CF parsing algorithms are first
presented in the form of a recognizer, and then the information
management needed to actually build parse trees and parse forests is
sort of added as an afterthought. One reason ...
9
Your understanding of dynamic programming is correct (afaik), and your question is justified.
I think the additional design space we get from the kind of recurrences we call "dynamic programming" can best be seen in comparison to other schemata of recursive approaches.
Let's pretend our inputs are arrays $A[1..n]$ for the sake of highlighting the concepts.
...
8
The Knapsack problem as defined in Karp's paper is NP-Complete since there is a reduction from other NPC problem (Exact Cover, in this case) to Knapsack. This means that there is no polynomial algorithm that can solve all instances of the Knapsack problem, unless $\text{P}=\text{NP}$.
There are, however, different variants (e.g., 0-1 Knapsack and others) ...
8
You can do it in $O(N \log N)$ time and $O(N)$ space.
Instead of finding the billboards that you want to keep, find the billboards that you want to get rid of. You need to find the minimum cost set of billboards such that there is no gap of more than $K$ between two billboards. Do this by constructing a table where the $i$th entry is the minimum cost to ...
8
The key to understanding a dynamic programing problem is understanding the recursive definition and this can be daunting. For this problem we start with n objects labeled 1 to n.
We define $O(K,W)$ to be the optimal value for the first k items with a total weight W, we need to be able to define this in terms of subproblems now since without that, dynamic ...
8
CYK is still relevant, afaik, as the simplest example of a family of general
parsing algorithm based on dynamic programming, ranging over all
parsing technique (that I know of) and many syntactic formalisms. There is a simpler
general parsing algorithm (below), but where the dynamic programming (DP)
aspect is no longer visible. as things are defined more ...
8
The picture should say more than words.
7
Actually, I don't believe your proposed solution is correct. An example where you might need this case
| # |
| # # #|
| # # #|
| # # #|
might be
| 1 2 1 1|
| 2 1 1 1|
| 1 1 1 2|
| 1 1 2 1|
The optimal solution consists of all 2s, while there are only 1s in the corners; therefore, you cannot find an optimal solution just by starting at the ...
7
If you just seek to speed up your recursive algorithm, memoisation might be enough. This is the technique of storing results of function calls so that future calls with the same parameters can just reuse the result. This is applicable if (and only if) your function
does not have side effects and
does only depend on its parameters (i.e. not on some state). ...
7
Dynamic programming is useful is your recursive algorithm finds itself reaching the same situations (input parameters) many times. There is a general transformation from recursive algorithms to dynamic programming known as memoization, in which there is a table storing all results ever calculated by your recursive procedure. When the recursive procedure is ...
7
As Bartek commented, you are missing a base case. You can compute large values of $T$ in several ways:
Bartek's suggestion: Use an array to store all the entries computed so far.
You can optimize the previous method, dramatically reducing the memory needed: store only the last $4$ entries of the array at each point in time.
Use matrix powering. There are ...
7
What you describe is a linear program. You can use the following formulation:
Let $x_i$ be the $i$th element. The variables are $d_1,\ldots, d_{n-1}$, where $d_i$ denotes difference between $x_{i+1}$ and $x_i$. You require $d_i\ge 0$.
If two elements $x_i,x_j$ should be at least within some distance $\ell^-_{ij}$, then you set
$$ d_i+d_{i+1}+\cdots +d_{j-1}...
7
Try choosing a random assignment.
7
A well-known example is the Held-Karp dynamic programming approach to solving the traveling salesman problem (TSP), running in $O(n^22^n)$ time and $O(n2^n)$ space. For more, see these notes.
Only top voted, non community-wiki answers of a minimum length are eligible
