Previous: Git Internals
Next: 简明Hoare Logic
Knight Dialer
2018-11-10
Below is my solution to Leetcode Problem 935. The code is much more concise than any DP solution I have seen so far. A rough analysis is given here: link.
class Solution(object):
def knightDialer(self, N):
"""
:type N: int
:rtype: int
"""
if N == 1:
return 10
n = 1
a, b, c, d = 4, 2, 2, 1
while n < N:
a, b, c, d = b * 2 + c * 2, a, a + d * 2, c
n += 1
return (a + b + c + d) % (10 ** 9 + 7)