[动态规划]leetcode 935 Knight Dialer

class Solution {
public:
    vector<vector<int>> next;
int knightDialer(int N) {
        next.resize(10);
        next[0] = { 4, 6 };
        next[1] = { 6, 8 };
        next[2] = { 7, 9 };
        next[3] = { 4, 8 };
        next[4] = { 0, 3, 9 };
        next[5] = { };
        next[6] = { 0, 1, 7 };
        next[7] = { 2, 6 };
        next[8] = { 1, 3 };
        next[9] = { 2, 4 };
        vector<vector<int>> dp(N + 1, vector<int>(10, 0));
        for(int i = 0;i <= 9; i++)
        {
            dp[1][i] = 1;
        }
        for(int n = 2; n <= N; n++)
        {
            for(int i = 0;i <= 9; i++)
            {
                for(auto& idx : next[i])
                {
                    dp[n][i] = (dp[n][i] + dp[n - 1][idx]) % 1000000007;
                }
            }
        }
        
        int res = 0;
        for(int i = 0;i <= 9;i++)
        {
            res = (res + dp[N][i])  % 1000000007;
        }
        
        return res;
    }
};