LC 0935 [M] Knight Dialer - ALawliet/algorithms GitHub Wiki
class Solution:
def knightDialer(self, n: int) -> int:
dp = [1] * 10 # if n=1: it can only dial the 1 number it is on
MOD = 10**9 + 7
# since we can only do n-1 hops, and we initialized n=1 above, we can just start at 2
for i in range(2, n+1):
old_dp = dp.copy() # use a 1D matrix copy with space: O(10*2) instead of 2D matrix with space: O(10*n)
# because we always iterate asc and store 2 states
dp[0] = old_dp[4] + old_dp[6]
dp[1] = old_dp[6] + old_dp[8]
dp[2] = old_dp[7] + old_dp[9]
dp[3] = old_dp[4] + old_dp[8]
dp[4] = old_dp[3] + old_dp[9] + old_dp[0]
dp[5] = 0
dp[6] = old_dp[1] + old_dp[7] + old_dp[0]
dp[7] = old_dp[2] + old_dp[6]
dp[8] = old_dp[1] + old_dp[3]
dp[9] = old_dp[2] + old_dp[4]
print(dp)
ans = sum(dp) % MOD
return ans