C语言重构【935】骑士拨号器

川长思鸟来 2022-11-08 14:25 95阅读 0赞

### 文章目录 ###

*   *   *   *  所有题目源代码：\[Git地址\](https://github.com/ch98road/leetcode)
             *  题目
             *  方案：
             *   *  复杂度计算

#### 所有题目源代码：[Git地址][Git] ####

#### 题目 ####

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

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3N5bXVhbXVh_size_16_color_FFFFFF_t_70]  
![在这里插入图片描述][20210314000243120.png]

这一次，我们将 “骑士” 放在电话拨号盘的任意数字键（如上图所示）上，接下来，骑士将会跳 N-1 步。每一步必须是从一个数字键跳到另一个数字键。
    
    每当它落在一个键上（包括骑士的初始位置），都会拨出键所对应的数字，总共按下 N 位数字。
    
    你能用这种方式拨出多少个不同的号码？
    
    因为答案可能很大，所以输出答案模 10^9 + 7。
    
     
    
    示例 1：
    
    输入：1
    输出：10
    示例 2：
    
    输入：2
    输出：20
    示例 3：
    
    输入：3
    输出：46
     
    
    提示：
    1 <= N <= 5000

#### 方案： ####

*  dp，按照题目要求来就可以了

class Solution
    { 
    public:
        int knightDialer(int n)
        { 
            if (n == 1)
                return 10;
            int sum = 0;
            int mod = 1e9+7;
            vector<vector<long>> dp(n, vector<long>(10, 0));
            //数组初始化
            for (int i = 0; i < 10; i++)
            { 
                dp[0][i] = 1;
            }
            //1=6、8
            //2=7、9
            //3=4、8
            //4=3、9、0
            //5=不可能跳到，不用考虑
            //6=1、7、0
            //7=2、6
            //8=1、3
            //9=2、4
            //0=4、6
            for (int i = 1; i < n; i++)
            { 
                dp[i][0] += (dp[i - 1][4]+dp[i - 1][6])%mod;
                dp[i][1] += (dp[i - 1][6]+dp[i - 1][8])%mod;
                dp[i][2] += (dp[i - 1][7]+dp[i - 1][9])%mod;
                dp[i][3] += (dp[i - 1][4]+dp[i - 1][8])%mod;
                dp[i][4] += (dp[i - 1][3]+dp[i - 1][9]+dp[i - 1][0])%mod;
                //5忽略
                dp[i][6] += (dp[i - 1][1]+dp[i - 1][7]+dp[i - 1][0])%mod;
                dp[i][7] += (dp[i - 1][2]+dp[i - 1][6])%mod;
                dp[i][8] += (dp[i - 1][1]+dp[i - 1][3])%mod;
                dp[i][9] += (dp[i - 1][2]+dp[i - 1][4])%mod;
            }
            for (int i = 0; i < 10; i++)
            { 
                sum = (sum+dp[n - 1][i])%mod;
            }
            return sum;
        }
    };

##### 复杂度计算 #####

*  时间复杂度：O(n)
 *  空间复杂度：O(n)

[Git]: https://github.com/ch98road/leetcode
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3N5bXVhbXVh_size_16_color_FFFFFF_t_70]: /images/20221023/69c3fea6fc164dde882b15395e310556.png
[20210314000243120.png]: /images/20221023/fb828c063a1046d7b6cbbd25b1e93fa0.png