파비의 매일매일 공부기록

2023.11.27 Today's Challenge 본문

Problem Solving/LeetCode

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
반응형

'Problem Solving > LeetCode' 카테고리의 다른 글

2023.11.29 Today's Challenge  (0) 2023.11.29
2023.11.28 Today's Challenge  (0) 2023.11.28
2023.11.26 Today's Challenge  (0) 2023.11.26
2023.11.25 Today's Challenge  (2) 2023.11.25
2023.11.24 Today's Challenge  (1) 2023.11.24
'Problem Solving/LeetCode' Related Articles more
Comments