【Lintcode】1707. Knight Dialer

题目地址：

https://www.lintcode.com/problem/knight-dialer/description

给定一个如下图所示的棋盘：
允许从任何一个点出发，每次只能像国际象棋里的马一样走“日”。走$N?1$步后，将其所有踩过的数字拼接起来，就得到了一个长度为$N$的序列。问长度为$N$的不同序列有多少个。将结果模$10^9+7$后返回。

思路是动态规划。设$f[i][j]$是跳$i$步能形成的、并且以$j$结尾的序列个数。那么$$f[i][j]=\sum _{u\to j}f[i?1][u]$$$u\to j$表示从$u$可以跳到$j$。初始$?j,f[0][j]=1$。代码如下：

import java.util.Arrays;public class Solution {
    /*** @param N: N* @return: return the number of distinct numbers can you dial in this manner mod 1e9+7*/public int knightDialer(int N) {
    // Write your code hereint MOD = (int) (1E9 + 7);// 存一下每个位置可以跳到哪些位置int[][] move = {
    {
    4, 6}, {
    6, 8}, {
    7, 9}, {
    4, 8}, {
    0, 3, 9}, {
    }, {
    0, 1, 7}, {
    2, 6}, {
    1, 3}, {
    2, 4}};// 这里可以滚动数组优化int[][] dp = new int[2][10];Arrays.fill(dp[0], 1);for (int i = 1; i < N; i++) {
    Arrays.fill(dp[i & 1], 0);for (int j = 0; j < 10; j++) {
    for (int prev : move[j]) {
    dp[i & 1][j] += dp[i - 1 & 1][prev];dp[i & 1][j] %= MOD;}}}long res = 0;for (int i = 0; i < 10; i++) {
    res += dp[N - 1 & 1][i];}return (int) (res % (1E9 + 7));}
}

时空复杂度$O(N)$。