2023.11.27 Today's Challenge

fabichoi 2023. 11. 27. 23:45

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

Knight Dialer - LeetCode

Can you solve this real interview question? Knight Dialer - The chess knight has a unique movement, it may move two squares vertically and one square horizontally, or two squares horizontally and one square vertically (with both forming the shape of an L)

leetcode.com

DP로 푸는 문제

class Solution:
    def knightDialer(self, n: int) -> int:
        @cache
        def dp(remain, square):
            if remain == 0:
                return 1
            ans = 0
            for next_square in jumps[square]:
                ans = (ans + dp(remain - 1, next_square)) % MOD

            return ans

        jumps = [
            [4, 6],
            [6, 8],
            [7, 9],
            [4, 8],
            [3, 9, 0],
            [],
            [1, 7, 0],
            [2, 6],
            [1, 3],
            [2, 4]
        ]
            
        ans = 0
        MOD = 10 ** 9 + 7
        for square in range(10):
            ans = (ans + dp(n-1, square)) % MOD

        return ans