109th LeetCode Weekly Contest Knight Dialer

A chess knight can move as indicated in the chess diagram below:

This time, we place our chess knight on any numbered key of a phone pad (indicated above), and the knight makes N-1 hops. Each hop must be from one key to another numbered key.

Each time it lands on a key (including the initial placement of the knight), it presses the number of that key, pressing N digits total.

How many distinct numbers can you dial in this manner?

Since the answer may be large, output the answer modulo 10^9 + 7.

Example 1:

Input: 1

Output: 10

Example 2:

Input: 2

Output: 20

Example 3:

Input: 3

Output: 46

Note:

1 <= N <= 5000

说就是一个马在键盘上跳，能得到多少种的数字，比如1就是不跳。。在原地就是0到9,10个数

那么可以看看，0这个位置只有4和6可以跳过来，1是6,8可以跳过来，5是不可能到的，所以就有下面的代码（参考别人的，自己写的不好看）

class Solution {

public:

    int mod = ;

    int dp[],dp2[];

    int knightDialer(int N) {

       for(int i=;i<=;i++){

            dp[i]=;

        }

        for(int i=;i<N;i++){

            dp2[] = (dp[]+dp[])%mod;

            dp2[] = (dp[]+dp[])%mod;

            dp2[] = (dp[]+dp[])%mod;

            dp2[] = (dp[]+dp[])%mod;

            dp2[] = ((dp[]+dp[])%mod+dp[])%mod;

            dp2[] = ;

            dp2[] = ((dp[]+dp[])%mod+dp[])%mod;

            dp2[] = (dp[]+dp[])%mod;

            dp2[] = (dp[]+dp[])%mod;

            dp2[] = (dp[]+dp[])%mod;

            for(int j=;j<=;j++){

                dp[j] = dp2[j];

            }

        }

        int result = ;

        for(int i=;i<=;i++){

            cout<<dp[i]<< " ";

            result += dp[i] %mod;

            result %= mod;

        }

        cout<<endl;

        return result;

    }

};

巴特西

109th LeetCode Weekly Contest Knight Dialer

最新文章

热门文章