Leetcode 972 Solution

This article provides solution to leetcode question 972 (knight-dialer)
Categories:
Tags:
Access this page by simply typing in "lcs 972" in your browser address bar if you have bunnylol configured.

https://leetcode.com/problems/knight-dialer

Solution

class Solution:
    def knightDialer(self, n: int) -> int:
        dp = [1] * 10

        moves = [
            [4, 6],
            [6, 8],
            [7, 9],
            [4, 8],
            [3, 9, 0],
            [],
            [1, 7, 0],
            [2, 6],
            [1, 3],
            [2, 4],
        ]

        new_dp = [0] * 10

        for _ in range(n - 1):
            for i in range(10):
                new_dp[i] = 0

            for i in range(10):
                for j in moves[i]:
                    new_dp[i] += dp[j]

            for i in range(10):
                dp[i] = new_dp[i] % 1000000007

        return sum(dp) % 1000000007