# Questions tagged [dynamic-programming]

The tag has no usage guidance.

54 questions
Filter by
Sorted by
Tagged with
2k views

283 views

### Find two sequences of integers that have sum N but that don't have sub-sequences starting at the head of equal sum

This question arose from a discussion between a friend and I. $A$ is a sequence of length $T$ where for any $a_i$ in $A$, $a_i \in \left\{{1, 2, 3}\right\}$ $B$ is a sequence of length $U$ where ...
105 views

### Box stacking problem, and variants

You are given $n$ boxes and want to stack them to make a tallest possible tower, but you can only stack a box on top of another if the base is smaller in both dimensions. This is a classic dynamic ...
116 views

### How to approach the “traveling salesman problem” with cost changing every time salesman reaches a new city

Let's say instead of finding the shortest path we have to maximize the profit in a year of the salesman under the following constraints. Salesman can go to a different city only on weekends, all ...
433 views

### extension for Levenshtein distance

I am looking for an extension for Levenshtein distance (Edit distance) for multi dimensional strings (2D and 3D). I am not sure if there is a formal definition for multi dimensional or not, but here ...
87 views

### Longest stack-sortable subsequence

Given an array of $n$ pairwise-different positive integers, the problem is to find the longest subsequence that is stack-sortable, i.e. avoiding the permutation pattern $231$. How fast can this ...
208 views

### Run Length eXtreme encoded length

In run length encoding (RLE) the code stream consists of pairs $(c_i,\ell_i)$, which is understood as writing the character $c_i$ repeatedly $\ell_i$ times. Consider the following "improvement" of ...
54 views

### Probabilistic linebreaking algorithm

I'm currently trying to implement this paper: Bouckaert, Remco R., A probabilistic line breaking algorithm, Gedeon, Tamás D. (ed.) et al., AI 2003: Advances in Artificial Intelligence. 16th ...
105 views

### Is scalable hardware support for LogCFL (= sAC^1) possible?

The (uniform) circuit classes $TC^0$, $NC^1$ and $sAC^1$ seem to lend themselves to efficient hardware implementation. But using an FPGA approach to create the circuits on the fly seems problematic, ...
171 views

### Paper regarding the complexity of the longest path problem on weighted directed graphs of bounded treewidth

I would like to cite a paper/report/etc that solves the following problem polynomially in $n$: Given a weighted directed graph $G=(V,E)$, $|V|=n$, of bounded treewidth $k \in \mathbb{N}$ and a source-...
145 views

### Computing unique subset intersections

Given a set S = {si : {zj : z ∈ N} }, what is a time-efficient algorithm for computing the unique sets of intersections of all of the subsets of S? As per @JeffE's comment below, there are edge ...