We’re rewarding the question askers & reputations are being recalculated! Read more.

Questions tagged [dynamic-programming]

Questions about problems that can be solved by combining recursively obtained solutions of subproblems.

144 questions with no upvoted or accepted answers
Filter by
Sorted by
Tagged with
9
votes
1answer
3k views

Finding the longest repeating subsequence

Given a string $s$, I would like to find the longest repeating (at least twice) subsequence. That is, I would like to find a string $w$ which is a subsequence (doesn't have to be a contiguous) of $s$ ...
8
votes
0answers
328 views

How can the shortest traveling salesman tour be found in $O(2^n poly(n))$ time and less than exponential space?

I'm stuck on problem 9.4 from The Nature of Computation which reads: Dynamic Salesman. A naive search algorithm for TSP takes $O(n!)$ time to check all tours. Use dynamic programming to reduce this ...
8
votes
0answers
609 views

Chained operations on sequences with two operators

Given a binary expresion tree, with addition and multiplication operations, how can we optimize it's evaluation? Can we learn from matrix chain multiplication? A generalization of matrix chain ...
7
votes
0answers
250 views

Can the solution to a POMDP be found using linear programming?

It is known that Markov decision processes (MDPs) can be solved using linear programming (see page 24 of Carlos Guestrin's PhD dissertation). The linear program is: $$min_{V(x)} \sum_x \alpha(x)V(x)\\...
6
votes
1answer
1k views

Dynamic programming: speed of top down vs bottom up approaches

I have just completed a dynamic programming exercise on LeetCode (Coin Change). I tried a top down approach, but it failed for the larger inputs, whereas the bottom up approach worked for all inputs. ...
5
votes
0answers
133 views

Count Wildcard Parenthesizations of a String

Let $\Sigma = \{ (, ), ? \}$ be an alphabet. For a given string $s \in \Sigma^*$, we denote by $f(s)$ the number of ways to replace each symbol $?$ either with $($ or with $)$ such that $s$ is ...
4
votes
0answers
68 views

Maximum weight independent set in a King's graph

I would like to find a maximum weight independent set in a finite section of a King's graph. For an $m\times n$ King's graph where $n \ll m$, we can use an $O(2^{2n} m)$ bitmask dynamic programming ...
4
votes
0answers
123 views

Sequence Alignment with Skips

In my thesis I am working on a problem connected with sequence alignment, in particular, I deal with the Dynamic Time Warping (DTW) algorithm (see this for more), which is used to evaluate the ...
4
votes
0answers
572 views

2D version of LeetCode house robber problem

The house robber problem of leetcode can be described as followed : A robber enters a colony of houses numbered from 1 to n. Every house has a number printed on the top of it. That number is the ...
4
votes
1answer
93 views

How to cluster similar objects into fixed size groups?

I have $n$ people each of which can meet on certain days of the week. I want to group them into $\frac{n}{k}$ groups of size $k$ such that all people in a group can meet on a day. eg - Suppose there ...
3
votes
0answers
42 views

Forbidden Sequence Dynamic Programming

Given a finite set $\Omega$, I have the following problem. Say there is a list of forbidden subsequences $F \subset \Omega \cup \Omega^2 \cup \Omega^3 \dots \Omega^\infty$, while we do not know the ...
3
votes
0answers
49 views

Sequence matching

Let $T$ and $P$ be respectively two sequences $t_1, · · · , t_n$ and $p_1, · · · , p_k$ of characters such that $k ≤ n$. The characters range over a finite alphabet Σ. With each position of $T$, we ...
3
votes
0answers
226 views

Sequence Alignment with general gap penalties: proof of optimal substructure

I am very well-aware of how optimal substructure for pairwise global sequence alignment using the Needleman-Wunsch algorithm works. However, I have merely seen hand-waving explanations for the ...
3
votes
0answers
72 views

What is the relationship between the Markov property and optimal substructure?

Dynamic programming can only be applied to problems with optimal substructure. The Markov property (e.g. in Markov Decision Processes, MDPs) means that the distribution of one state $x_{k+1}$ only ...
3
votes
0answers
1k views

can we solve dynamic knapsack problem using Memoization approach?

As we know Dynamic programming has two techniques. Bottom up dynamic programming approach. Top down memoization approach Normally dynamic knapsack problem is solved using Bottom up dynamic ...
3
votes
0answers
329 views

Does the Longest Common Subsequence problem reduce to its binary version?

I am working on a problem regarding the Longest Common Subsequence (LCS) of two strings, and I was wondering if there is any reduction from the general case of LCS to its binary version, i.e. by ...
3
votes
0answers
510 views

When not to use dynamic programming

I was reading about dynamic programming and I understood that we should not be using dynamic programming approach if the optimal solution of a problem does not contain the optimal solution of the ...
3
votes
0answers
813 views

Finding the n-best items in a 0/1 Knapsack

I'm trying to understand why an alternate formula for finding the best $p$ items in a 0/1 knapsack with $n$ items isn't working. The formula was proposed by @Carlos Linares López in this answer: ...
3
votes
0answers
363 views

Algorithms that are similar to Dynamic TIme Warping

Dynamic time warping (DTW) is an algorithm in time series analysis for measuring similarity between two temporal sequences which may vary in time or speed. Here are some explanations of DTW: Dynamic ...
3
votes
1answer
220 views

Number of “hamiltonian tours” from upper left to lower left corner of a grid graph?

I got the following as an interview question: Count the number of tours from the upper left corner to the lower left corner in a grid world where you can move in any manhattan direction. This is the ...
2
votes
1answer
41 views

Multiple choice knapsack dynamic problem

Giving a the following: A list of a store items $T=\{t_1, t_2,...,t_n\}$. A list of prices of each item $P=\{p_1, p_2,...,p_n\}$. A list of quantities of each item $Q=\{q_1, q_2,...,q_n\}$...
2
votes
1answer
23 views

Minimum words in a string given a dictionary

The question is: Given a dictionary consisting of a set of words and a string: find the minimum number of words the string can be split into. If the string can not be decomposed into a list of words ...
2
votes
0answers
19 views

Seeking an algorithm for finding the partition of data on an interval that maximizes the minimum fitness among the blocks

In the paper "An algorithm for optimal partitioning of data on an interval" (link) the authors describe an algorithm for partitioning data on an interval to maximize a fitness function. The fitness ...
2
votes
0answers
33 views

Dynamic Program for this Weighted Possion-Binomial Problem?

Setup: Suppose we have $n$ independent Bernoulli random variables, say $\boldsymbol{X} = \{X_1, ..., X_n\}$ each with prior $\mathbb{P}(X_j = 1) = p_j$, and weights between $-1$ and $1$, say $W = \{...
2
votes
0answers
23 views

Selecting objects to maximize value while under multiple constraints

I think it will be best to explain the problem first and then explain what I am thinking: I have a dataset similar to the following: ...
2
votes
2answers
82 views

How can I solve this problem using dynamic programming?

I'm stuck in this problem and I would need some help: Given an array arr, in each step, 1, 2 or 5 units have to be incremented to all but one item of the array. ...
2
votes
1answer
144 views

Task Distribution Algorithm

Different machine has different efficiency on different tasks, like: ...
2
votes
0answers
100 views

Join Order Optimization

Consider the join: (σtitle=Overwatch Game)⨝ Event ⨝ rating ⨝ Player What is the optimal join order? Based on the schema on the following picture: I am suppoused (and that's what I tried) to use ...
2
votes
0answers
68 views

Minimum number of deleting palindromes to delete whole string

Let's say we have given array $A$ of size $n$. Our goal is to delete the whole array with minimum steps. In one step we can choose substring (consecutive elements from the string) and delete it only ...
2
votes
0answers
190 views

Maximize interleaving subsequences two digit arrays/strings

Suppose I have two digit arrays, A and B as follows A = [3,4,5,6] B = [9,8,3] Now, I have ...
2
votes
1answer
43 views

Max sum cyclic path of fixed length in matrix

Given a matrix NxM of positive integer values and a starting position (that has value 0), determine the maximum sum path of length K that starts and ends at the aforementioned position. Legal moves ...
2
votes
1answer
132 views

What is the optimal way to perform GCD chain operation?

Matrix chain multiplication problem:- Given a sequence of matrices, the goal is to find the most efficient way to multiply these matrices. This problem is solved using dynamic programming. Similarly ...
2
votes
0answers
30 views

What are the pros and cons of context-oriented programming (COP)?

I have started reading about COP, but can't really get a grip of it. What I understand is that you use layers to let the software dynmically adapt depending on the context, and this would result in ...
2
votes
0answers
73 views

Balls in Bins with Pairwise Distance

Given $n$ bins in a row (numbering from $1$ to $n$) and $2k$ balls ($n \ge 2k$), one may put all balls into bins with each bin having at most one ball (there are $\binom{n}{2k}$ configurations). ...
2
votes
0answers
155 views

Tail recursion can't work with dynamic programming programs

I am doing some exercises on dynamic programming in order to get familar with this concept. I've noticed that most of the time it's not difficult to calculate the complexity of a program using dynamic ...
2
votes
0answers
109 views

Weighted Sorting Algorithm

Given a permutation of $n$ element and for each pair of position $i$ and $j$, a non-negative integer $c_{ij}$ which is cost of swapping $i$-th element and $j$-th element of permutation. Is there any ...
2
votes
0answers
120 views

Is there a pseudo polynomial time algorithm for this 0-1 quadratic subset sum problem?

Say that we have some (integer) weights $w_{1,1},w_{1,2},...,,w_{m,m}$ and a target sum $W$. Suppose that we want to find whether there are $a_1,...,a_m \in \{0,1\}$ such that $$\sum_{i = 1}^{m} \...
2
votes
0answers
34 views

Static management of dynamic memory

I have some issue but I can't identify a way to solve it. I wanted to ask you what kind of problem it is? We have a resource - contiguous computer memory. Also we have users which require some ...
2
votes
0answers
113 views

Coloring of a K-ary tree using minimum paint Buckets

I was recently asked this problem in an interview and I couldn't solve it. Need some help on how to solve this problem. Given a K-ary tree with N nodes (N <= 2000 and K <= 12) you need to ...
2
votes
0answers
100 views

Shortest sequence over alphabet $\{1, 2, …, k\}$ which is not a subsequence of $A$ and $B$

I have two sequences - $A$ (of length $n$) and $B$ (of length $m$). They consist of numbers from the alphabet $\{1, 2, ..., k\}$. How want to find the shortest sequence $C$ such that $C$ is not a ...
2
votes
0answers
110 views

One variant of the Knapsack Problem

We have a normal knapsack problem but we can choose up to $t_i$ of the $i$-th object. How would you solve this problem with complexity less than $O(V(n + \sigma(t_i)))$ where $n$ is number of objects ...
2
votes
0answers
59 views

How to compare A* with DP approach in finding shortest Path?

Consider a hypercube defined over $n$ dimensions where the edges are associated to strictly positive weights, and nodes are marked with $n$ bit-strings, e.g. the source is marked as (0,0,0) in a 3-...
2
votes
0answers
133 views

Given a set of integers $S$ and a target number $T$, find a subset of $S$ that adds up exactly to $T$ in $O(nT)$ time

Given a set of integers $S=\{s_1,s_2,...,s_n\}$ and a target number $T$, find a subset of $S$ that adds up exactly to $T$ in $O(nT)$ time. I am not quite sure how to solve this but I think I have the ...
2
votes
0answers
83 views

Finding maximum information gain subinterval of an array containing points from 2 classes

Suppose we have an $N \times 2$ array $A$ where the two entries $A(k,1)$ and $A(k,2)$ give the number of occurrences of each of two classes at position $k$. Given a sub-interval $I$ of indices between ...
2
votes
0answers
48 views

Training a model to match two time series

Context I have two related time series, I want to learn to produce one from the other. However, they aren't synchronous, and the lag between the two does not revert to the mean, it accumulates. ...
2
votes
0answers
580 views

Job scheduling problem in O(n log n)

There are $n \leq 10^6$ kinds of cake layers, and for each kind we have a machine capable of baking it in one unit of time and nothing more. Now, a cake is a sequence of layers, more specificly a ...
1
vote
0answers
31 views

Weighted Activity Selection Problem with allowing shifting starting time

I have some activities with weights, and I would like to select non overlapping activities by maximizing the total weight. This is known problem and solution exists. In my case, I am allowed to ...
1
vote
0answers
11 views

Dancing Links use in tiling problems

I'm using Knuth's Dancing Links (dlx) algorithm to solve for solutions to tiling a 2xN rectangle using 3 different pieces of one, two, or three squares. It's working correctly in its basic form but ...
1
vote
0answers
36 views

How does the asterisk (*) work in the wildcard matching problem?

This is a wildcard matching problem. Given a pattern P containing letters and character * that can match an arbitrary string of characters (including an empty string), my task is to write a polynomial-...
1
vote
0answers
27 views

Determining the DP subproblem given a problem

I'm reviewing DP and I was wondering the intuition behind determining the subproblems for some DP problems. For example, consider 2 similar problems. Given a set of 1, 2, and 3 steps you can take, ...