# LeetCode 935: Knight Dialer

## Problem Restatement

We place a chess knight on a phone keypad.

The keypad is arranged like this:

```text
1 2 3
4 5 6
7 8 9
  0
```

The knight moves in the same L-shape as in chess.

We may start on any digit from `0` to `9`.

Each time the knight lands on a digit, that digit is pressed.

Given an integer `n`, return how many distinct phone numbers of length `n` can be dialed.

Since the answer can be large, return it modulo:

```python
10**9 + 7
```

The official statement asks for the number of length `n` phone numbers that can be dialed by starting on any digit and making `n - 1` valid knight jumps.

## Input and Output

| Item | Meaning |
|---|---|
| Input | Integer `n` |
| Output | Number of valid phone numbers of length `n` |
| Start | Any digit from `0` to `9` |
| Move | Valid chess knight jump on the keypad |
| Modulo | `10^9 + 7` |

Function shape:

```python
class Solution:
    def knightDialer(self, n: int) -> int:
        ...
```

## Examples

Example 1:

```python
n = 1
```

We can choose any single digit.

There are `10` possible numbers:

```text
0, 1, 2, 3, 4, 5, 6, 7, 8, 9
```

Answer:

```python
10
```

Example 2:

```python
n = 2
```

We choose a starting digit, then make one knight jump.

The valid moves are:

```python
0 -> 4, 6
1 -> 6, 8
2 -> 7, 9
3 -> 4, 8
4 -> 0, 3, 9
5 -> no moves
6 -> 0, 1, 7
7 -> 2, 6
8 -> 1, 3
9 -> 2, 4
```

There are `20` valid two-digit numbers.

Answer:

```python
20
```

Example 3:

```python
n = 3
```

The answer is:

```python
46
```

These are the standard examples for this problem.

## First Thought: Generate All Numbers

A direct approach is to try every possible starting digit and recursively follow every valid knight jump.

For each path of length `n`, we count one number.

This works for small `n`.

But the number of paths grows quickly. We do not need to build the actual numbers. We only need to count how many ways end at each digit after each length.

## Key Insight

This is dynamic programming on a small graph.

Each digit is a node.

Each valid knight jump is an edge.

Let:

```python
dp[digit]
```

mean the number of valid numbers of the current length that end at `digit`.

For length `1`, every digit has exactly one way:

```python
dp = [1] * 10
```

For each next length, we compute a new array.

If we are currently at digit `d`, then all counts at `d` can move to every digit in `moves[d]`.

## Algorithm

Use this move table:

```python
moves = {
    0: [4, 6],
    1: [6, 8],
    2: [7, 9],
    3: [4, 8],
    4: [0, 3, 9],
    5: [],
    6: [0, 1, 7],
    7: [2, 6],
    8: [1, 3],
    9: [2, 4],
}
```

Initialize:

```python
dp = [1] * 10
```

Then repeat `n - 1` times:

1. Create `next_dp = [0] * 10`.
2. For each digit `d`, distribute `dp[d]` to every valid next digit.
3. Replace `dp` with `next_dp`.

Finally return:

```python
sum(dp) % MOD
```

## Walkthrough

Use:

```python
n = 2
```

For length `1`:

```python
dp = [1, 1, 1, 1, 1, 1, 1, 1, 1, 1]
```

Each digit is one possible one-digit number.

Now build length `2`.

From digit `0`, we can go to `4` and `6`.

So:

```text
next_dp[4] += 1
next_dp[6] += 1
```

From digit `1`, we can go to `6` and `8`.

So:

```text
next_dp[6] += 1
next_dp[8] += 1
```

After processing all digits, the total number of length `2` numbers is:

```python
20
```

## Correctness

For length `1`, `dp[digit] = 1` is correct because there is exactly one number of length `1` ending at each digit: the digit itself.

Assume `dp[d]` correctly stores the number of valid numbers of the current length ending at digit `d`.

To form a number with one more digit, the knight must jump from the current ending digit `d` to some valid next digit `next_digit`.

For each valid move `d -> next_digit`, every number counted in `dp[d]` creates one new valid number ending at `next_digit`.

The algorithm adds exactly those counts into `next_dp[next_digit]`.

No invalid number is counted, because the algorithm only follows valid knight moves.

No valid number is missed, because every valid number of the next length has a previous digit and a final knight jump from that previous digit.

Therefore, after each iteration, `dp` contains the correct counts for that length.

After building length `n`, summing all entries gives the total number of valid phone numbers of length `n`.

## Complexity

| Metric | Value | Why |
|---|---|---|
| Time | `O(n)` | There are only 10 digits and a constant number of moves |
| Space | `O(1)` | The DP arrays always have length 10 |

## Implementation

```python
class Solution:
    def knightDialer(self, n: int) -> int:
        MOD = 10**9 + 7

        moves = [
            [4, 6],
            [6, 8],
            [7, 9],
            [4, 8],
            [0, 3, 9],
            [],
            [0, 1, 7],
            [2, 6],
            [1, 3],
            [2, 4],
        ]

        dp = [1] * 10

        for _ in range(n - 1):
            next_dp = [0] * 10

            for digit in range(10):
                for next_digit in moves[digit]:
                    next_dp[next_digit] = (next_dp[next_digit] + dp[digit]) % MOD

            dp = next_dp

        return sum(dp) % MOD
```

## Code Explanation

The modulo is required because the count can become very large:

```python
MOD = 10**9 + 7
```

The move table stores valid knight jumps from each digit:

```python
moves = [
    [4, 6],
    [6, 8],
    [7, 9],
    [4, 8],
    [0, 3, 9],
    [],
    [0, 1, 7],
    [2, 6],
    [1, 3],
    [2, 4],
]
```

The base case is length `1`:

```python
dp = [1] * 10
```

Every digit can be chosen as the first digit.

For each additional digit, we build a new DP array:

```python
next_dp = [0] * 10
```

Then we distribute counts along valid moves:

```python
for digit in range(10):
    for next_digit in moves[digit]:
        next_dp[next_digit] = (next_dp[next_digit] + dp[digit]) % MOD
```

Finally, all counts for length `n` are summed:

```python
return sum(dp) % MOD
```

## Testing

```python
def run_tests():
    s = Solution()

    assert s.knightDialer(1) == 10
    assert s.knightDialer(2) == 20
    assert s.knightDialer(3) == 46
    assert s.knightDialer(4) == 104

    print("all tests passed")

run_tests()
```

| Test | Why |
|---|---|
| `n = 1` | Any digit is valid |
| `n = 2` | One knight jump |
| `n = 3` | Standard sample |
| `n = 4` | Checks repeated DP transitions |