935. Knight Dialer

# time O(N) space O(N)
class Solution:
    def knightDialer(self, n: int) -> int:
        dp = [[[0]*3 for _ in range(4)] for _ in range(n+1)]
        self.m = 10**9+7
        self.dir = [(-1,-2),(-1,2),(1,-2),(1,2),(-2,-1),(-2,1),(2,-1),(2,1)]
        res = 0
        for i in range(4):
            for j in range(3):
                res = (res + self.dfs(dp,i,j,n)) % self.m
        return res
    def dfs(self,dp,i,j,n):
        if i < 0 or i >=4 or j < 0 or j >= 3 or (i==3 and j !=1) :
            return 0
        if n == 1:
            return 1
        if dp[n][i][j]: 
            return dp[n][i][j]
        for d in self.dir:
            dp[n][i][j] += self.dfs(dp,i+d[0],j+d[1],n-1)% self.m
        return dp[n][i][j]

class Solution:
    def knightDialer(self, n: int) -> int:
        self.m = 10**9+7
        g = [(4,6),（6,8), (7,9), (4,8), (3,9,0), (), (1,7,0), (2,6), (1,3), (2,4)]
        res = 0
        memo = [[0]*10 for _ in range(n+1)]
        for i in range(10): 
            res = (res + self.dfs(i,g,n,memo)) % self.m
        return res
    def dfs(self,cur,g,n,memo):
        if n == 1:
            return 1
        if memo[n][cur] != 0: 
            return memo[n][cur]
        cnt = 0
        for nei in g[cur]:
            cnt = (cnt + self.dfs(nei,g,n-1,memo))% self.m
        memo[n][cur] = cnt 
        
        return cnt