935. Knight Dialer - Explanation

class Solution:
    def knightDialer(self, n: int) -> int:
        if n == 1:
            return 10

        mod = 1000000007
        jumps = [
            [4, 6], [6, 8], [7, 9], [4, 8], [0, 3, 9],
            [], [0, 1, 7], [2, 6], [1, 3], [2, 4]
        ]

        def dfs(n, d):
            if n == 0:
                return 1

            res = 0
            for j in jumps[d]:
                res = (res + dfs(n - 1, j)) % mod
            return res

        res = 0
        for d in range(10):
            res = (res + dfs(n - 1, d)) % mod
        return res

class Solution:
    def knightDialer(self, n: int) -> int:
        if n == 1:
            return 10

        mod = 1000000007
        jumps = [
            [4, 6], [6, 8], [7, 9], [4, 8], [0, 3, 9],
            [], [0, 1, 7], [2, 6], [1, 3], [2, 4]
        ]

        dp = [[-1] * (n + 1) for _ in range(10)]

        def dfs(n, d):
            if n == 0:
                return 1
            if dp[d][n] != -1:
                return dp[d][n]

            dp[d][n] = 0
            for j in jumps[d]:
                dp[d][n] = (dp[d][n] + dfs(n - 1, j)) % mod
            return dp[d][n]

        res = 0
        for d in range(10):
            res = (res + dfs(n - 1, d)) % mod
        return res

class Solution:
    def knightDialer(self, n: int) -> int:
        if n == 1:
            return 10

        mod = 1000000007
        jumps = [
            [4, 6], [6, 8], [7, 9], [4, 8], [0, 3, 9],
            [], [0, 1, 7], [2, 6], [1, 3], [2, 4]
        ]

        dp = [[0] * (n + 1) for _ in range(10)]

        for d in range(10):
            dp[d][0] = 1

        for step in range(1, n):
            for d in range(10):
                dp[d][step] = sum(dp[j][step - 1] for j in jumps[d]) % mod

        return sum(dp[d][n - 1] for d in range(10)) % mod

class Solution:
    def knightDialer(self, n: int) -> int:
        if n == 1:
            return 10

        mod = 1000000007
        jumps = [
            [4, 6], [6, 8], [7, 9], [4, 8], [0, 3, 9],
            [], [0, 1, 7], [2, 6], [1, 3], [2, 4]
        ]

        dp = [1] * 10
        for step in range(n - 1):
            next_dp = [0] * 10
            for d in range(10):
                for j in jumps[d]:
                    next_dp[j] = (next_dp[j] + dp[d]) % mod
            dp = next_dp

        res = 0
        for d in dp:
            res = (res + d) % mod
        return res

class Solution:
    def knightDialer(self, n: int) -> int:
        if n == 1:
            return 10

        mod = 10**9 + 7
        jumps = [1, 4, 2, 2]  # [D, A, B, C]

        for _ in range(n - 1):
            tmp = [0] * 4
            tmp[0] = jumps[3]
            tmp[1] = 2 * jumps[2] + 2 * jumps[3]
            tmp[2] = jumps[1]
            tmp[3] = 2 * jumps[0] + jumps[1]
            jumps = tmp

        return sum(jumps) % mod

class Matrix:
    def __init__(self, size):
        self.n = size
        self.a = [[0] * size for _ in range(size)]

    def __mul__(self, other):
        n = self.n
        MOD = 10**9 + 7
        product = Matrix(n)
        for i in range(n):
            for j in range(n):
                for k in range(n):
                    product.a[i][k] = (product.a[i][k] + self.a[i][j] * other.a[j][k]) % MOD
        return product


def matpow(mat, n, size):
    res = Matrix(size)
    for i in range(size):
        res.a[i][i] = 1  # Identity matrix

    while n:
        if n & 1:
            res = res * mat
        mat = mat * mat
        n >>= 1

    return res


class Solution:
    def knightDialer(self, n: int) -> int:
        if n == 1:
            return 10

        MOD = 10**9 + 7
        jumps = [
            [4, 6], [6, 8], [7, 9], [4, 8], [0, 3, 9],
            [], [0, 1, 7], [2, 6], [1, 3], [2, 4]
        ]

        mat = Matrix(10)
        for i in range(10):
            for j in jumps[i]:
                mat.a[i][j] = 1

        res = matpow(mat, n - 1, 10)

        ans = sum(sum(res.a[i]) for i in range(10)) % MOD
        return ans