  Dynamic time warping distance (DTW) is a widely used distance measure between
time series. The best known algorithms for computing DTW run in near quadratic
time, and conditional lower bounds prohibit the existence of significantly
faster algorithms. The lower bounds do not prevent a faster algorithm for the
special case in which the DTW is small, however. For an arbitrary metric space
$\Sigma$ with distances normalized so that the smallest non-zero distance is
one, we present an algorithm which computes $\operatorname{dtw}(x, y)$ for two
strings $x$ and $y$ over $\Sigma$ in time $O(n \cdot \operatorname{dtw}(x,
y))$. We also present an approximation algorithm which computes
$\operatorname{dtw}(x, y)$ within a factor of $O(n^\epsilon)$ in time
$\tilde{O}(n^{2 - \epsilon})$ for $0 < \epsilon < 1$. The algorithm allows for
the strings $x$ and $y$ to be taken over an arbitrary well-separated tree
metric with logarithmic depth and at most exponential aspect ratio. Extending
our techniques further, we also obtain the first approximation algorithm for
edit distance to work with characters taken from an arbitrary metric space,
providing an $n^\epsilon$-approximation in time $\tilde{O}(n^{2 - \epsilon})$,
with high probability. Additionally, we present a simple reduction from
computing edit distance to computing DTW. Applying our reduction to a
conditional lower bound of Bringmann and K\"unnemann pertaining to edit
distance over $\{0, 1\}$, we obtain a conditional lower bound for computing DTW
over a three letter alphabet (with distances of zero and one). This improves on
a previous result of Abboud, Backurs, and Williams. With a similar approach, we
prove a reduction from computing edit distance to computing longest LCS length.
This means that one can recover conditional lower bounds for LCS directly from
those for edit distance, which was not previously thought to be the case.
