333. Mobile Numeric Keypad Problem

A standard mobile numeric keypad (digits 1-9 in a 3x3 grid, with 0 below the 8) lets you move from the currently pressed digit to itself, or to any digit directly above, below, left, or right of it on the keypad (no diagonal moves; moves off the edge of the keypad aren't allowed). Given n, count the number of distinct sequences of exactly n key presses obtainable this way, starting from any digit.

Input: A single line contains the integer n, the number of key presses. Output: Print a single integer - the total count of distinct length-n sequences obtainable on the keypad.

1 <= n <= 10^4

The keypad's fixed, small adjacency structure (never changing regardless of n) is what makes this problem's DP transition genuinely O(1) per digit per step - the graph itself doesn't grow, only the sequence LENGTH does.

Count the distinct sequences of exactly n key presses achievable on a numeric keypad, moving only to adjacent digits. Brute force: Try every possible sequence of n key presses directly, checking adjacency at each step - this is exponential (up to 10^n sequences, though many are invalid), impractical for larger n without a systematic count. Optimised: Since a length-i sequence ending on digit d is built by extending a length-(i-1) sequence ending on any digit adjacent to d, this DP directly counts valid sequences without generating them explicitly - each dp[d][i] value only depends on the PREVIOUS length's dp values, letting the table be built one length at a time.

Use the same recursive exploration of reachable digits, but cache the count of valid sequences for each (current digit, presses remaining) pair the first time it's computed, so repeated calls with the same state return immediately. Since there are only 10 digits and n possible remaining-press counts, there are only O(10*n) distinct states, each computed once from already-solved smaller states. Time: O(10*n) Space: O(10*n)

Maintain an array of 10 counts representing, for the current number of presses so far, how many sequences end at each digit; initialize it with all 1s for a single press. For each subsequent press, build a new array of 10 counts where each digit's new count is the sum of the previous counts of that digit and all its keypad neighbors, then replace the old array with the new one. Repeating this n-1 times and summing the final array gives the total sequence count, using only two small fixed-size arrays instead of a full memo table indexed by press count. Time: O(n) (constant work per step since there are only 10 digits) Space: O(1) (two arrays of fixed size 10)

Starting from every digit 0-9 as a possible first press, recursively try every digit reachable from the current digit (itself, up, down, left, or right on the keypad, ignoring moves off the grid) for each of the remaining n-1 presses, counting a complete sequence whenever n presses have been made. Because the same (digit, presses-remaining) state is reached via many different paths and none of the results are cached, the same subproblems get recomputed repeatedly. Time: O(4^n) roughly (branching factor up to ~4-5 per digit) Space: O(n) recursion depth

1. dp[d][i] = number of length-i sequences ending on digit d; dp[d][1]=1 for every digit d. 2. dp[d][i] = sum of dp[d'][i-1] over every digit d' that can move TO d (which, since adjacency is symmetric, is the same set of digits d can move to). 3. The keypad's adjacency is fixed and small enough to hardcode directly (e.g., 5 connects to {2,4,6,8}, 0 connects only to {8}, 1 connects to {2,4}, no diagonal to 5); the final answer sums dp[d][n] over all ten digits.

Time: O(n * average keypad degree) - for each of the n lengths, updating all 10 digits' counts based on their small, fixed neighbor sets. Space: O(10) per length (or O(10*n) if the full table is stored, though only the previous length's row is actually needed).

Test n = 1 (10 sequences, one per starting digit) and n = 10^4 (upper bound), which requires the O(n) digit-adjacency DP rather than enumerating sequences directly.

Be ready to state the exact keypad adjacency explicitly (which digits connect to which) - getting this hardcoded mapping wrong (especially the no-diagonal-moves rule, and 0 connecting only to 8) is the most common source of bugs in this problem.