935 骑士拨号器

题目链接

935. 骑士拨号器

分析

可以发现，对于原问题，在进行一次移动后，化为了规模更小但和原问题类似的子问题，使用记忆化搜索即可

定义 $f[x][y]$，表示在 $y$ 号键上移动 $x$ 次的电话数

递归搜索，注意在相加时要转换成 $long \ long$ 再取余数保证数据不越界

代码实现

class Solution {
public:
    const int MOD = 1e9 + 7;
    const vector<int> dir[10] = {{4, 6}, {6, 8}, {7, 9}, {4, 8}, {0, 3, 9}, {}, {0, 1, 7}, {2, 6}, {1, 3}, {2, 4}};
    int f[5005][10] = {0};
  
    int knightDialer(int n) {
        if(n == 1)
            return 10;
  
        auto dfs = [&](auto& dfs, int num, int time) -> int {
            if(time == 1)
                return 1;
            if(f[time][num])
                return f[time][num];
  
            int ret = 0;

            for(int i : dir[num])
                ret = (1ll * dfs(dfs, i, time - 1) + ret) % MOD;
  
            f[time][num] = ret;
            return ret;
        };

        int ans = 0;

        for(int i = 0; i < 10; ++i)
            ans = (1ll * ans + dfs(dfs, i, n)) % MOD;

        return ans;
    }
};

复杂度分析

• 时间复杂度：$O(nC)$，其中 $C = 9$
• 空间复杂度：$O(nC)$