Problem
https://leetcode.com/problems/knight-dialer/description/
A chess knight can move as indicated in the chess diagram below:
.
This time, we place our chess knight on any numbered key of a phone pad (indicated above), and the knight makes N-1
hops. Each hop must be from one key to another numbered key.
Each time it lands on a key (including the initial placement of the knight), it presses the number of that key, pressing N
digits total.
How many distinct numbers can you dial in this manner?
Since the answer may be large, output the answer modulo 10^9 + 7
.
Example 1:
Input: 1 Output: 10
Example 2:
Input: 2 Output: 20
Example 3:
Input: 3 Output: 46
Note:
1 <= N <= 5000
Solution: DP
V1
Similar to 花花酱 688. Knight Probability in Chessboard
We can define dp[k][i][j] as # of ways to dial and the last key is (j, i) after k steps
Note: dp[*][3][0], dp[*][3][2] are always zero for all the steps.
Init: dp[0][i][j] = 1
Transition: dp[k][i][j] = sum(dp[k – 1][i + dy][j + dx]) 8 ways of move from last step.
ans = sum(dp[k])
Time complexity: O(kmn) or O(k * 12 * 8) = O(k)
Space complexity: O(kmn) -> O(mn) or O(12*8) = O(1)
V2
define dp[k][i] as # of ways to dial and the last key is i after k steps
init: dp[0][0:10] = 1
transition: dp[k][i] = sum(dp[k-1][j]) that j can move to i
ans: sum(dp[k])
Time complexity: O(k * 10) = O(k)
Space complexity: O(k * 10) -> O(10) = O(1)
C++ V1
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 |
// Author: Huahua, 96 ms class Solution { public: int knightDialer(int N) { constexpr int kMod = 1e9 + 7; int dirs[8][2] = {{-2, -1}, {-2, 1}, {-1, -2}, {-1, 2}, {1, -2}, {1, 2}, {2, -1}, {2, 1}}; vector<vector<int>> dp(4, vector<int>(3, 1)); dp[3][0] = dp[3][2] = 0; for (int k = 1; k < N; ++k) { vector<vector<int>> tmp(4, vector<int>(3)); for (int i = 0; i < 4; ++i) for (int j = 0; j < 3; ++j) { if (i == 3 && j != 1) continue; for (int d = 0; d < 8; ++d) { int tx = j + dirs[d][0]; int ty = i + dirs[d][1]; if (tx < 0 || ty < 0 || tx >= 3 || ty >= 4) continue; tmp[i][j] = (tmp[i][j] + dp[ty][tx]) % kMod; } } dp.swap(tmp); } int ans = 0; for (int i = 0; i < 4; ++i) for (int j = 0; j < 3; ++j) ans = (ans + dp[i][j]) % kMod; return ans; } }; |
C++ V2
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 |
// Author: Huahua, 24 ms public: int knightDialer(int N) { constexpr int kMod = 1e9 + 7; vector<vector<int>> moves{{4,6},{8,6},{7,9},{4,8},{3,9,0},{},{1,7,0},{2,6},{1,3},{2,4}}; vector<int> dp(10, 1); for (int k = 1; k < N; ++k) { vector<int> tmp(10); for (int i = 0; i < 10; ++i) for (int nxt : moves[i]) tmp[nxt] = (tmp[nxt] + dp[i]) % kMod; dp.swap(tmp); } int ans = 0; for (int i = 0; i < 10; ++i) ans = (ans + dp[i]) % kMod; return ans; } }; |