Questions tagged [dynamic-programming]

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

155 questions with no upvoted or accepted answers
Filter by
Sorted by
Tagged with
9
votes
1answer
4k 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
356 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
255 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)\\...
5
votes
0answers
74 views

Find the 'best' longest common subsequence

I am writing a program that computes and displays diffs. I implemented Meyers algorithm that computes the LCS between 2 subsequences (seq1 and ...
5
votes
0answers
137 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 ...
5
votes
1answer
2k 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. ...
4
votes
0answers
65 views

Assign n people to m rooms of different sizes, such that noone is alone

I'm looking for an efficient way to assign n people to m rooms in a very specific way. INPUT: The program receives two sets of people (set of males and set of females), as well as a set of available ...
4
votes
0answers
78 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
128 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
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 ...
4
votes
0answers
577 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
120 views

Making an array increasing by modifying elements

I am trying to solve a problem on codeforces. Given an integer array $a_1,\ldots,a_n$, our goal is to find the minimal number of instructions, each of which increments or decrements a single entry, ...
3
votes
0answers
44 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
50 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
229 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
73 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
339 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
539 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
836 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
371 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
238 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
0answers
31 views

Algebraic Dynamic Programming breakdown of a simple problem (e.g. climbing staircase)

I found recently about Algebraic Dynamic Programming. As I understand, it's a formalization that immensely simplifies developing solutions for DP problems. I spent a few days trying to grok it, to no ...
2
votes
0answers
20 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
26 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
87 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
186 views

Task Distribution Algorithm

Different machine has different efficiency on different tasks, like: ...
2
votes
0answers
101 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
79 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
193 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
46 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
147 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
32 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
74 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
172 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
124 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
1k views

k-way set partition problem--dynamic programming solution

I was reading up on the set partition problem on this site of Wikipedia: https://en.m.wikipedia.org/wiki/Partition_problem Among other things, they present a DP approach to solving the equal subset ...
2
votes
0answers
480 views

Solving a Rod Cutting Problem

I'm trying to come up with an algorithm for optimizing cutting a rod. Most of the examples I see online are for a stock of rod of a single length and optimizing the way to cut it up for max price. I ...
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
118 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
102 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
117 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
60 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
135 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
588 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 ...