How to Learn Dynamic Time Warping (DTW): Cost Matrices, Warping Paths, Step Constraints, Sakoe–Chiba Bands and Production Sequence Alignment

Wait, What?

Two sequences can describe the same event even when one happens faster, pauses longer, or stretches different parts of time.

If two signals have equal length and are perfectly synchronized, comparing position 1 with position 1, position 2 with position 2 and so on makes sense. Real sequences are often less cooperative. One person speaks a word quickly and another slowly. Two gestures contain the same phases at different speeds. Two machine cycles have the same shape but one lingers during a transition.

Dynamic Time Warping, or DTW, replaces rigid lockstep comparison with an alignment path through a cost matrix. The path can move diagonally, horizontally or vertically under defined rules, allowing one sample in one sequence to align with multiple nearby samples in the other.

For a beginner, DTW is a grid-path problem. At intermediate level, the key ideas are local costs, dynamic programming and backtracking. At advanced level, you need step patterns, window constraints and normalization. At professional level, the crucial questions are feature scaling, endpoint semantics, lower bounds, memory, missing data, reproducibility and whether warping is scientifically meaningful for the domain.

Quick Answer

Learn DTW in this order: lockstep sequence distance → local pairwise cost → n×m cost matrix → dynamic-programming recurrence → boundary, monotonicity and continuity constraints → recover the warping path → understand horizontal/vertical repeats → choose a step pattern → add a Sakoe–Chiba window when justified → distinguish global and subsequence DTW → reduce memory when only distance is needed → normalize features and distance carefully → validate against exhaustive small cases and a trusted library → use lower bounds and indexing for large search workloads.

1. Start with the failure of lockstep distance

Suppose:

X = [1, 2, 2, 3]
Y = [1, 1, 2, 3]

A position-by-position absolute difference gives:

|1-1| + |2-1| + |2-2| + |3-3| = 1

But the sequences have the same progression: 1 → 2 → 3. They simply repeat different stages.

DTW asks whether the sequences can be aligned by locally stretching the index axis while preserving order.

2. Build a local cost matrix

For sequences:

X = (x1, x2, ..., xn)
Y = (y1, y2, ..., ym)

define a local cost:

c(i,j) = d(x_i, y_j)

For scalar data, d might be absolute difference or squared difference. For feature vectors, it might be Euclidean distance, cosine-derived cost or another domain-appropriate measure.

The local metric is part of the model. DTW does not choose it for you.

3. The classic dynamic-programming recurrence

A common symmetric DTW recurrence is:

D[i,j] = c(i,j) + min(
    D[i-1,j],
    D[i,j-1],
    D[i-1,j-1]
)

with suitable boundary initialization.

The three predecessor moves mean:

diagonal: advance in both sequences;
vertical: advance in X while holding Y’s index;
horizontal: advance in Y while holding X’s index.

Those non-diagonal moves create the time warping.

4. A DTW path is an ordered correspondence

A warping path is a sequence of matrix cells:

(i1,j1), (i2,j2), ..., (iK,jK)

that obeys the chosen boundary and step rules.

In the classic full-sequence form, the path begins at (1,1) and ends at (n,m). Indices never move backward. Each step is local.

This gives three core constraints:

boundary: align the intended endpoints;
monotonicity: preserve sequence order;
continuity: move only through allowed local steps.

5. A zero-cost worked example

Using absolute difference with:

X = [1, 2, 2, 3]
Y = [1, 1, 2, 3]

one valid path is:

(1,1)
(1,2)
(2,3)
(3,3)
(4,4)

The aligned pairs are:

Every local absolute difference is zero, so this path has total cost zero.

This example also exposes an important fact: standard DTW can assign zero distance to two distinct sequences. DTW distance is therefore not automatically a mathematical metric.

6. Fill the matrix from smaller prefixes

Each cell D[i,j] represents the best cost of aligning the relevant prefixes of X and Y under the chosen recurrence.

Because each cell depends only on earlier neighbors, the matrix can be filled row by row or column by column.

This is ordinary dynamic-programming structure:

state      = prefix endpoints (i,j)
choice     = predecessor step
transition = local cost + best predecessor
answer     = terminal state

7. Backtracking recovers the actual alignment

The final accumulated distance tells you the best score, but it does not tell you which samples aligned.

To recover the path, begin at the terminal cell and repeatedly choose the predecessor that produced the optimum until the start is reached.

If path interpretation matters, store predecessor decisions or retain enough of the matrix to recompute them reliably.

A distance-only implementation can use much less memory than a path-producing implementation.

8. O(nm) is the classic baseline

For sequences of lengths n and m, unconstrained classic DTW examines O(nm) cells.

If the full accumulated-cost matrix is stored, memory is also O(nm).

If only the final distance is required, each row depends mainly on the current and previous row, so memory can often be reduced to O(min(n,m)) by orienting the shorter sequence across the rolling dimension.

Path reconstruction changes that memory story.

9. Step patterns define which warpings are legal

The simple three-neighbor recurrence is not the only DTW formulation. Different step patterns can weight moves differently or restrict how many consecutive horizontal or vertical steps are possible.

This affects:

which alignments are admissible;
how path length influences cost;
whether one sequence can be stretched heavily relative to the other;
what normalization is appropriate.

A professional report should name the step pattern, not merely say “we used DTW.”

10. The local cost is not the final distance

A learner may confuse c(i,j), the cost of aligning one pair of samples, with D[i,j], the accumulated best path cost to that state.

Keep separate notation:

c = local mismatch
D = accumulated dynamic-programming cost

This small notation discipline prevents many implementation errors.

11. Sakoe–Chiba bands limit excessive warping

A Sakoe–Chiba band restricts the path to cells near the main diagonal, commonly expressed as:

|i - j| ≤ r

or a scaled equivalent when lengths differ.

The band says: “the sequences may drift, but not arbitrarily far apart in time.”

With a narrow band, far fewer matrix cells need evaluation. If the band width is r, work can approach O(nr) for similarly sized sequences rather than O(nm).

12. A window is a modeling assumption, not just an optimization

If the unconstrained optimal path leaves the band, a Sakoe–Chiba constraint changes the answer.

That may be desirable because extreme warping is scientifically implausible. Or it may discard the true alignment.

Choose window width from domain knowledge, validation data or a stated search procedure. Do not present it as a free speedup.

13. Itakura-style constraints are another possibility

Other global constraints, such as the Itakura parallelogram, limit path slope rather than using one fixed diagonal radius.

The important learning point is not memorizing every shape. It is recognizing that a global path constraint expresses assumptions about how quickly one sequence is allowed to run ahead of the other.

14. Subsequence DTW changes the endpoint contract

Sometimes the task is not to align all of X with all of Y. Instead, a short query may need to find its best-matching region inside a longer recording.

Subsequence DTW changes boundary initialization and termination so that the path can begin or end at flexible positions in the longer sequence.

Do not use full-sequence endpoint rules and call the result subsequence matching. The boundary condition is part of the algorithm.

15. Multivariate DTW needs feature design

If each time step contains a feature vector:

x_i ∈ R^d

then local cost depends on a vector distance.

Features with large numerical scales can dominate Euclidean distance. Before DTW, decide whether to standardize, normalize, whiten, weight or transform features based on the domain.

A perfect dynamic-programming implementation cannot rescue a meaningless local metric.

16. Sampling rate and time units matter

Two sequences sampled at 100 Hz and 1 kHz do not become comparable merely because DTW accepts unequal lengths.

Resampling, filtering and time calibration may be needed first. Otherwise, the path can compensate for an acquisition mismatch that should have been corrected upstream.

Warping is not a substitute for knowing what the time axis means.

17. Normalization must be stated explicitly

Raw accumulated cost usually grows with path length. Applications sometimes divide by path length, sequence length or another normalization factor.

Different step patterns can make different normalization choices appropriate.

Therefore, record:

local distance function;
step pattern and step weights;
global window;
endpoint rule;
distance normalization.

Without those details, two reported “DTW distances” may not be comparable.

18. DTW is generally not a metric

Under common formulations, DTW can violate metric properties. Distinct sequences can have zero DTW distance when repetitions align away, and the triangle inequality need not hold.

This matters in data structures and machine learning because some nearest-neighbor indexes assume metric geometry.

Before plugging DTW into a metric tree or theorem, verify that the method’s assumptions still hold.

19. Lower bounds can prune expensive comparisons

For large nearest-neighbor search tasks, computing full DTW against every candidate may be too expensive.

Lower bounds such as LB_Keogh can cheaply prove that a candidate cannot beat the current best DTW score under compatible settings. If the lower bound is already worse than the best-so-far threshold, the full dynamic program can be skipped.

This is a powerful professional pattern: exact search can become much faster by using a cheap admissible filter before the expensive exact computation.

20. Early abandoning needs a threshold

If a search already has a best-so-far distance, rows or active cells whose lower achievable cost exceeds that threshold may sometimes be abandoned, depending on the recurrence and implementation.

The threshold must be used conservatively. An optimization that incorrectly prunes a possible better path changes an exact algorithm into an approximate one.

21. Missing values require a policy

NaN or missing samples can propagate through local-cost calculations and poison the entire dynamic-programming matrix.

Possible policies include:

impute before alignment;
mask dimensions with an adjusted local cost;
reject sequences with missing values;
define an explicit missingness penalty.

There is no universal correct choice. It depends on what missingness means in the measurement process.

22. Numerical range can become a problem

Long sequences and squared local costs can create very large accumulated values. Floating-point infinity sentinels are common, but NaNs, overflow in integer implementations and inconsistent precision can still cause failures.

Test long high-cost sequences and document the numeric type used for accumulation.

23. Ties can produce multiple optimal paths

Several predecessors may yield the same accumulated cost. The distance is unchanged, but the recovered alignment path can differ depending on tie-breaking order.

If path interpretation is scientifically important, define deterministic tie-breaking and record it. Otherwise, two implementations can report equal DTW distance but different alignments.

24. A strong teaching sequence starts with a drawn grid

Before code, draw X down one axis and Y across the other. Put a small local cost in every cell.

Predict: point to cells that should align semantically.
Trace: fill the accumulated-cost matrix from the top-left.
Explain: say what diagonal, horizontal and vertical moves mean.
Modify: add a narrow band and identify which paths become illegal.
Build: implement the recurrence only after the grid can be explained.

This follows programming-education evidence favoring worked examples, explicit subgoals and structured movement from prediction and tracing toward independent implementation.

25. Use subgoal labels for the dynamic-programming procedure

A useful set of subgoals is:

define the sequence elements and local distance;
initialize impossible boundaries;
compute each local cost;
choose the best legal predecessor;
store accumulated cost;
read the terminal distance;
backtrack if a path is required.

Subgoal labels help learners see one reusable dynamic-programming architecture rather than a wall of nested loops.

26. Build a tiny exhaustive oracle

For sequences of length only a few elements, enumerate every legal monotone path and compute its cost directly.

Then compare:

dtw_dynamic_programming(X,Y) == min(cost(path) for every legal path)

This is slower than DTW, but excellent for testing the DTW implementation on small states.

27. Backtracked paths have invariants

For classic full-sequence DTW, assert that:

the path starts at the required start cell;
the path ends at the required terminal cell;
indices never decrease;
each step belongs to the allowed step set;
every path cell lies inside the global window if one is active;
the sum of path costs matches the reported accumulated cost under the chosen weights.

Testing the path catches bugs that a final scalar distance can hide.

28. Cross-check a trusted library

Libraries such as librosa expose DTW with configurable step sizes, weights, global constraints and subsequence behavior.

Use an independent library to cross-check small deterministic examples while keeping your own oracle and invariants. Matching one implementation is not a proof, but disagreement is a valuable debugging signal.

29. Adversarial test families

Include:

identical sequences;
constant sequences;
one-element sequences;
very unequal lengths;
repeated plateaus;
large isolated outliers;
noisy resampled copies;
paths forced against the edge of a window;
cases where a narrow band makes alignment impossible;
multivariate features with radically different scales;
ties with multiple optimal paths;
NaNs or missing values according to the chosen policy.

30. Compare DTW with neighboring methods

Euclidean or lockstep distance: appropriate when timestamps are already aligned and local time distortion should not be allowed.

Edit distance: designed for discrete symbol insertions, deletions and substitutions rather than continuous-valued temporal alignment.

Viterbi/HMM alignment: uses a probabilistic state model and transition structure; it answers a different modeling question.

Cross-correlation: useful for a more global lag or shift rather than arbitrary local stretching.

Soft-DTW: replaces the hard minimum with a smooth alternative useful in differentiable optimization, but it is not identical to classic DTW.

31. Production monitoring should measure more than runtime

Record:

sequence lengths;
number of evaluated matrix cells;
window width;
path length;
fraction of horizontal, vertical and diagonal moves;
raw and normalized distance;
lower-bound pruning rate in search systems;
early-abandon rate;
memory allocated;
feature scaling version and preprocessing version.

Extreme warping ratios can be a useful diagnostic that the model is aligning things that should not be considered equivalent.

32. When DTW is the wrong tool

Avoid unconstrained DTW when:

absolute timing differences are themselves meaningful;
local repetition should count as a mismatch rather than be warped away;
sequence length is so large that O(nm) work is unacceptable and constraints cannot be justified;
features do not have a meaningful local distance;
the task requires a probabilistic generative interpretation;
the application needs metric-distance guarantees.

The professional skill is not merely knowing how to run DTW. It is knowing when time warping is a legitimate invariance.

33. Beginner-to-professional learning ladder

Beginner: draw a cost grid and interpret horizontal, vertical and diagonal steps.
Foundation: fill the classic recurrence by hand and backtrack one optimal path.
Intermediate: implement full DTW and a rolling-row distance-only version.
Advanced: reason about step patterns, normalization, Sakoe–Chiba windows, subsequence boundaries and non-metric behavior.
Professional: define feature semantics, use lower bounds and pruning, handle missing data and ties, validate with exhaustive oracles and trusted libraries, and document every alignment constraint needed for reproducibility.

34. Ownership boundary

This article owns the public learning job for Dynamic Time Warping as an elastic sequence-alignment algorithm: local cost matrices, warping paths, dynamic-programming recurrence, step constraints, Sakoe–Chiba bands, subsequence variants, memory reduction and production validation. It complements broader dynamic-programming and sequence-modeling material and does not redefine HMM/Viterbi learning, learner-state systems, assessment calibration, studying interfaces or any private implementation machinery elsewhere in the eduKate ecosystem.

Sources and further reading

Hiroaki Sakoe and Seibi Chiba, “Dynamic Programming Algorithm Optimization for Spoken Word Recognition,” IEEE Transactions on Acoustics, Speech, and Signal Processing 26(1), 1978: DOI.
librosa 0.11.0, current DTW documentation including custom steps, global constraints and subsequence matching: librosa.
Eamonn Keogh and Chotirat Ann Ratanamahatana, “Exact Indexing of Dynamic Time Warping,” Knowledge and Information Systems, 2005: DOI.
IBM Research, “Memory and Time Improvements in a Dynamic Programming Algorithm for Matching Speech Patterns”: IBM Research.
ACM/IEEE-CS/AAAI CS2023, Algorithms and Complexity knowledge area: CS2023.
Computer Science Teachers Association, 2026 standards overview emphasizing algorithms and the progression from reading and evaluating to modifying, debugging and creating programs: CSTA.
Sentance, Waite and Kallia, PRIMM programming pedagogy: SIGCSE.
Margulieux, Morrison and Decker, subgoal-labeled worked examples in introductory programming: International Journal of STEM Education.

Professional rule: you understand DTW when you can explain not only which path is cheapest, but what every allowed warp means in the real process that produced the sequence.

Small Group Tutorials