New answers tagged dynamic-programming
0
Denote the two strings by $s = s_1,\ldots, s_n$ and $t = t_1,\ldots, t_m$. Let $\mathcal{U}(i,j)$ denote the multiset of common subsequences of $s_1,\ldots,s_i$ and $t_1,\ldots,t_j$ which contain $s_i$ and $t_j$. Let $\mathcal{U}(\leq i,j)$ be the union of $\mathcal{U}(I,j)$ over all $i \leq I$, and define $\mathcal{U}(i,\leq j),\mathcal{U}(\leq i, \leq j)$ ...
0
The most common subproblems where a particular subsequence should be selected are parametrized by the index of the last element selected. The classical, simple and brilliant example is Kadane's algorithm.
Let the given intervals are $I_1, I_2,\cdots, I_n$, where $I_j=[l_j, r_j]$.
The subproblem $DP[i]$, where $1\le i\le n$ is the maximum rent if the last ...
0
This can be solved in $\mathcal{O}(n\log^2{}n)$ by using a 2D-range query data structure to optimize the Dynamic Programming solution which has been explained in the link given in the question:
As in the link, for a box in the input with dimensions $(w_i, d_i, h_i)$, consider all rotations of the box, but maintain the property that the first dimension is ...
1
Suppose the gap between any two words in the same line spans a length of $k$, instead of 1. The only change needed in the Python code would be to change the line in def cost(i, j) from
w = offsets[j] - offsets[i] + j - i - 1
to
w = offsets[j] - offsets[i] + k * (j - i - 1)
def cost(i, j) returns the minimum cost needed for placing the first $j$ words, if ...
3
I think there is some confusion in terminology here. Part of the problem is what we mean by problem and what we mean by an algorithm. But there is more to it:
Textbooks like CLRS introduce the notion of optimal substructure as a property of problems (and not algorithms directly). That's because an algorithm often transforms a problem statement into other ...
2
Dynamic programming is an algorithmic technique, algorithms are classified as dynamic programming according to what their high-level structure "looks like", not according to a formal definition. If you really wanted to, you could force some sorting algorithms to fit into the dynamic-programming paradigm.
Let $A[1:n]$ be the array to sort, assume for ...
1
One simple algorithm is as follows. Start by choosing the dumbbell which is going to have the minimum weight (we are going to try all possibilities). Then take the $M$ dumbbells with maximal rep among those with weight above the minimum weight (if there are enough).
To implement this algorithm efficiently, start by sorting the dumbbells according to weight ...
1
In general, you would change the question slightly: "How many ways are there to tile an X by N area by adding tiles individually and always adding the next tile so that it covers the topmost of the leftmost uncovered squares". Obviously that doesn't change the number of possible tilings at all since each square must eventually be covered.
Since you are ...
3
Here is a systematic way to approach it. I suggest you define three values:
$A_0(n)$ is the number of ways to tile a $3 \times n$ region.
$A_1(n)$ is the number of ways to tile a $3 \times n$ region with the upper-left cell already covered.
$A_2(n)$ is the number of ways to tile a $3 \times n$ region with the upper-left cell and the cell to the right of ...
1
In CC you can use same coin INFINITE times. But in KP you can use the same weight, not more than once. Check http://www.ccs.neu.edu/home/jaa/CSG713.04F/Information/Handouts/dyn_prog.pdf
To consider all the subsets of items, there can be two cases for every item:
(1) the item is included in the optimal subset
(2) not included in the optimal set.
...
3
Memoization is the technique to "remember" the result of a computation, and reuse it the next time instead of recomputing it, to save time. It does not care about the properties of the computations.
Dynamic programming is the research of finding an optimized plan to a problem through finding the best substructure of the problem for reusing the computation ...
1
What about the array $[1, 3, 5]$? The supersequence $[0,1,0,3,0,5]$ is oscillating while the original sequence isn’t. In fact you can make an oscillating supersequence of any array by inserting $\min(arr)-1$ before every element of the original array.
4
Let $g(i,j)$ be the gas consumed when travelling to destination $i$ with car $j$.
Guess the optimal order $\langle c_1, c_2, c_3 \rangle$ of cars (there are only $3! = 6$ possible permutations).
Define $OPT[i,j]$ as the minimum amount of gas needed for reaching the first $i$ destinations using cars $c_1, \dots, c_j$ in this order, with the constraint that ...
4
The optimization function is designed in a way to find a solution that:
uses a small number of lines
is balanced (the number of extra spaces at the end of each line should be about the same length)
Lets look first at the linear optimization function, i.e. the sum of all extra spaces.
It is very clear, that the optimal solution under that function is one ...
2
Let $N(t,S)$ be the least number of values from $S$ which sum to $t$. The basic recurrence is
$$
N(t, S \cup \{s\}) = \min(N(t,S),N(t-s,S)+1).
$$
I'll let you work out the details.
This recurrence leads to an efficient algorithm only if we are allowed to run in time polynomial in $t$.
If we think of $t$ encoded in binary, then this algorithm runs in ...
1
Let $M=\max_i|A_i|$.
Besides the linear programming method proposed in this post (which is suitable for small $N$ and large $M,H$), you can optimize your dynamic programming method by building a larger table to reduce the time for querying the minimum value among $f(i-1,j-H),\ldots,f(i-1,j+H)$.
Let $f(i,j,k)$ be the minimum moves to stabilize the first $i$...
Top 50 recent answers are included
