import numpy as np

class DTW:

    def __init__(self, n, m):
        cdef double[:, :] dp = np.ones((n + 1, m + 1)) * float('inf')
        self.dp   = dp
        self.n    = n
        self.m    = m

    def clear(self):
        self.dp * float('inf')
        self.dp[0,0] = 0

    def dtw(self, x, y):
        assert len(x) == self.n and len(y) == self.m
        cdef int i, j
        cdef double dist
        self.clear()
        for i in range(1, self.n):
            for j in range(1, self.m):
                dist = np.sum(np.square(x[i - 1] - y[j - 1]))
                self.dp[i, j] = dist + min([
                    self.dp[i - 1, j    ],
                    self.dp[i    , j - 1],
                    self.dp[i - 1, j - 1]
                ])
        return self.dp[self.n, self.m]