LeetCode 935. 骑士拨号器    原题链接    中等

作者： 作者的头像   wzc1995 ,  2018-11-18 05:03:56 ,  所有人可见 ,  阅读 1433

1


题目描述

国际象棋中的骑士可以按下图所示进行移动：


这一次，我们将 “骑士” 放在电话拨号盘的任意数字键（如上图所示）上，接下来，骑士将会跳 N-1 步。每一步必须是从一个数字键跳到另一个数字键。

每当它落在一个键上（包括骑士的初始位置），都会拨出键所对应的数字，总共按下 N 位数字。

你能用这种方式拨出多少个不同的号码？

因为答案可能很大，所以输出答案模 10^9 + 7。

样例

输入: 1
输出: 10

输入: 2
输出: 20

输入: 3
输出: 46

注意

  • 1 <= N <= 5000

算法

(动态规划) $O(n)$
  1. 设 $f(i, j)$ 表示走了 $i$ 步，当前数字为 $j$ 的不同的方案数。
  2. 转移时，枚举每个数字分别能从哪里跳过来，直接累加即可，即 $f(i, j) = f(i, j) + f(i - 1, k)$，其中 $k$ 能跳到 $j$。
  3. 初始值 $f(0, j) = 1$，最终答案为 $\sum_{j=0}^{10}{f(n - 1, j)}$。

时间复杂度

  • 共计 $10n$ 个状态，每次转移也是常数个，故时间复杂度为 $O(n)$。

C++ 代码

class Solution {
public:
    int knightDialer(int N) {
        vector<int> a[10];
        a[0].push_back(4); a[0].push_back(6);
        a[1].push_back(6); a[1].push_back(8);
        a[2].push_back(7); a[2].push_back(9);
        a[3].push_back(4); a[3].push_back(8);
        a[4].push_back(3); a[4].push_back(9); a[4].push_back(0);
        a[6].push_back(1); a[6].push_back(7); a[6].push_back(0);
        a[7].push_back(2); a[7].push_back(6);
        a[8].push_back(1); a[8].push_back(3);
        a[9].push_back(2); a[9].push_back(4);

        vector<vector<int>> f(N, vector<int>(10, 0));
        int mod = 1000000007;

        for (int j = 0; j < 10; j++)
            f[0][j] = 1;

        for (int i = 1; i < N; i++)
            for (int j = 0; j < 10; j++)
                for (int k = 0; k < a[j].size(); k++)
                    f[i][j] = (f[i][j] + f[i - 1][a[j][k]]) % mod;

        int ans = 0;
        for (int j = 0; j < 10; j++)
            ans = (ans + f[N - 1][j]) % mod;

        return ans;
    }
};

3 评论

用户头像
acwing_6775   12天前         踩      回复

``` #include [HTML_REMOVED]
#include [HTML_REMOVED]
using namespace std;

class Solution {
public:
int knightDialer(int N) {
// 定义骑士移动规则
vector[HTML_REMOVED]> moves = {{4, 6}, {6, 8}, {7, 9}, {4, 8}, {3, 9, 0},
{}, {1, 7, 0}, {2, 6}, {1, 3}, {2, 4}};

    const int mod = 1e9 + 7;
    vector<long long> dp(10, 0), dpPrev(10, 1);

    for (int step = 1; step < N; ++step) {
        for (int i = 0; i < 10; ++i) {
            dp[i] = 0;
            for (int next : moves[i]) {
                dp[i] = (dp[i] + dpPrev[next]) % mod;
            }
        }
        dp.swap(dpPrev); // 更新到下一步
    }

    // 计算所有可能的结尾位置之和
    return accumulate(dpPrev.begin(), dpPrev.end(), 0LL) % mod;
}

};```

用户头像
acwing_6775   12天前         踩      回复

#include [HTML_REMOVED]
#include [HTML_REMOVED]
using namespace std;

class Solution {
public:
int knightDialer(int N) {
// 定义骑士移动规则
vector[HTML_REMOVED]> moves = {{4, 6}, {6, 8}, {7, 9}, {4, 8}, {3, 9, 0},
{}, {1, 7, 0}, {2, 6}, {1, 3}, {2, 4}};

    const int mod = 1e9 + 7;
    vector<long long> dp(10, 0), dpPrev(10, 1);

    for (int step = 1; step < N; ++step) {
        for (int i = 0; i < 10; ++i) {
            dp[i] = 0;
            for (int next : moves[i]) {
                dp[i] = (dp[i] + dpPrev[next]) % mod;
            }
        }
        dp.swap(dpPrev); // 更新到下一步
    }

    // 计算所有可能的结尾位置之和
    return accumulate(dpPrev.begin(), dpPrev.end(), 0LL) % mod;
}

};

用户头像
All_The_Way_North   2021-07-08 20:01         踩      回复

大神 latex语法有点小问题 $\sum_{j=0}^{10}{f(n - 1, j)}。