935. 骑士拨号器

题目描述

象棋骑士有一个独特的移动方式，它可以垂直移动两个方格，水平移动一个方格，或者水平移动两个方格，垂直移动一个方格 (两者都形成一个 L 的形状)。

象棋骑士可能的移动方式如下图所示:

我们有一个象棋骑士和一个电话垫，如下所示，骑士只能站在一个数字单元格上 (即蓝色单元格)。

给定一个整数 n，返回我们可以拨多少个长度为 n 的不同电话号码。

你可以将骑士放置在任何数字单元格上，然后你应该执行 n - 1 次移动来获得长度为 n 的号码。所有的跳跃应该是有效的骑士跳跃。

因为答案可能很大，所以输出答案模 10⁹ + 7.

示例 1：

输入：n = 1
输出：10
解释：我们需要拨一个长度为1的数字，所以把骑士放在10个单元格中的任何一个数字单元格上都能满足条件。

示例 2：

输入：n = 2
输出：20
解释：我们可以拨打的所有有效号码为[04, 06, 16, 18, 27, 29, 34, 38, 40, 43, 49, 60, 61, 67, 72, 76, 81, 83, 92, 94]

示例 3：

输入：n = 3131
输出：136006598
解释：注意取模

提示：

1 <= n <= 5000

解法一：动态规划

 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
30
31


func knightDialer(n int) int {
    const MOD = 1e9 + 7
    // dp[i][j] 表示经过 n- 1 次移动后 ，停留在数字 j 的方案数。
    dp := make([][]int, n+1)
    for i := 0; i <= n; i++ {
        dp[i] = make([]int, 10)
    }
    for j := 0; j < 10; j++ {
        dp[1][j] = 1
    }
    for i := 2; i <= n; i++ {
        dp[i][0] = dp[i-1][4] + dp[i-1][6]
        dp[i][1] = dp[i-1][6] + dp[i-1][8]
        dp[i][2] = dp[i-1][7] + dp[i-1][9]
        dp[i][3] = dp[i-1][4] + dp[i-1][8]
        dp[i][4] = (dp[i-1][0]+dp[i-1][3])%MOD + dp[i-1][9]
        dp[i][6] = (dp[i-1][0]+dp[i-1][1])%MOD + dp[i-1][7]
        dp[i][7] = dp[i-1][2] + dp[i-1][6]
        dp[i][8] = dp[i-1][1] + dp[i-1][3]
        dp[i][9] = dp[i-1][2] + dp[i-1][4]
        for j := 0; j < 10; j++ {
            dp[i][j] %= MOD
        }
    }
    ans := 0
    for j := 0; j < 10; j++ {
        ans += dp[n][j]
        ans %= MOD
    }
    return ans
}

另一种实现代码：

 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


func knightDialer(n int) int {
    const MOD = 1e9 + 7
    var dp [2][]int
    dp[0], dp[1] = make([]int, 10), make([]int, 10)
    for j := 0; j < 10; j++ {
        dp[0][j] = 1
    }
    // moves[i] 存储的是可以移动到数字 i 的数字
    moves := [][]int{{4, 6}, {6, 8}, {7, 9}, {4, 8}, {0, 3, 9}, {}, {0, 1, 7}, {2, 6}, {1, 3}, {2, 4}}
    for i := 0; i < n-1; i++ {
        for curNum, prevNums := range moves {
            dp[1][curNum] = 0
            for _, prevNum := range prevNums {
                dp[1][curNum] = (dp[1][curNum] + dp[0][prevNum]) % MOD
            }
        }
        // error: dp[0] = dp[1] 是让 dp[0] 和 dp[1] 引用同一个切片，应该使用 copy
        // dp[0] = dp[1]
        copy(dp[0], dp[1])
    }
    ans := 0
    for j := 0; j < 10; j++ {
        ans += dp[0][j]
        ans %= MOD
    }
    return ans
}