<p>The chess knight has a <strong>unique movement</strong>,&nbsp;it may move two squares vertically and one square horizontally, or two squares horizontally and one square vertically (with both forming the shape of an <strong>L</strong>). The possible movements of chess knight are shown in this diagram:</p>

<p>A chess knight can move as indicated in the chess diagram below:</p>
<img alt="" src="https://assets.leetcode.com/uploads/2020/08/18/chess.jpg" style="width: 402px; height: 402px;" />
<p>We have a chess knight and a phone pad as shown below, the knight <strong>can only stand on a numeric cell</strong>&nbsp;(i.e. blue cell).</p>
<img alt="" src="https://assets.leetcode.com/uploads/2020/08/18/phone.jpg" style="width: 242px; height: 322px;" />
<p>Given an integer <code>n</code>, return how many distinct phone numbers of length <code>n</code> we can dial.</p>

<p>You are allowed to place the knight <strong>on any numeric cell</strong> initially and then you should perform <code>n - 1</code> jumps to dial a number of length <code>n</code>. All jumps should be <strong>valid</strong> knight jumps.</p>

<p>As the answer may be very large, <strong>return the answer modulo</strong> <code>10<sup>9</sup> + 7</code>.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>

<pre>
<strong>Input:</strong> n = 1
<strong>Output:</strong> 10
<strong>Explanation:</strong> We need to dial a number of length 1, so placing the knight over any numeric cell of the 10 cells is sufficient.
</pre>

<p><strong class="example">Example 2:</strong></p>

<pre>
<strong>Input:</strong> n = 2
<strong>Output:</strong> 20
<strong>Explanation:</strong> All the valid number we can dial are [04, 06, 16, 18, 27, 29, 34, 38, 40, 43, 49, 60, 61, 67, 72, 76, 81, 83, 92, 94]
</pre>

<p><strong class="example">Example 3:</strong></p>

<pre>
<strong>Input:</strong> n = 3131
<strong>Output:</strong> 136006598
<strong>Explanation:</strong> Please take care of the mod.
</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>1 &lt;= n &lt;= 5000</code></li>
</ul>

class Solution {
public:
    /*bool isValid(int r, int c){
        return (r>=0 && c>=0 && r<4 && c<3 && (r!=3 || c==1)); 
    }

    int dx[8]= {-2, -2, -1, -1, 1, 1, 2, 2}; 
    int dy[8] = {-1, 1, 2, -2, 2, -2, 1, -1}; 

    int mod = 1e9+7; 

    int solve(int n, int length, vector<vector<char>>& grid, int row, int col, vector<vector<vector<int>>>& dp){
        if(length==n){
            return 1;  
        }
        if(dp[row][col][length] != -1) return dp[row][col][length]; 
        int cnt=0; 
        for(int i=0; i<8; i++){
            int nrow = row+dx[i]; 
            int ncol = col+dy[i]; 
            if(isValid(nrow, ncol)){
                cnt = (cnt+solve(n, length+1, grid, nrow, ncol, dp))%mod; 
            }
        }
        return dp[row][col][length] = cnt; 
    }*/
    int mod = 1e9+7; 
    int solve(int number, int length, vector<vector<int>>& arr, int n, vector<vector<int>>& dp){
        if(length==n){
            return 1; 
        }
        if(dp[number][length]!=-1) return dp[number][length]; 

        int cnt=0; 
        if(dp[number][length]!=-1) return dp[number][length]; 

        for(int it: arr[number]){
            cnt = (cnt+solve(it, length+1, arr, n, dp))%mod; 
        }

        return dp[number][length] = cnt; 
    }
    int knightDialer(int n) {
        /*if(n==1) return 10; 
        vector<vector<char>> grid(4, vector<char>(3)); 
        char arr[12] = {'1','2','3','4','5','6','7','8','9','*','0','#'}; 

        int index=0; 
        for(int i=0; i<4; i++){
            for(int j=0; j<3; j++){
                grid[i][j] = arr[index]; 
                index++; 
            }
        }
        //4,6 - three moves
        // 0,1,2,3,7,8,9 - two moves 
        // 5 - no moves 
        vector<vector<vector<int>>> dp(4, vector<vector<int>> (3, vector<int>(5001, -1))); 
        int ans=0; 

        for(int i=0; i<4; i++){
            for(int j=0; j<3; j++){
                if((i==3 && j==0) || (i==3 && j==2) || (i==1 && j==1)){
                    continue; 
                }
                ans = (ans+solve(n, 0, grid, i, j, dp))%mod; 
            }
        }
        return ans; */
        if(n==1) return 10; 
        vector<vector<int>> arr = {{4,6}, {6,8}, {7,9}, {4,8}, {0,3,9}, {}, {0,1,7}, {2,6}, {1,3}, {2,4}}; 
        int ans=0; 
        vector<vector<int>> dp(10, vector<int>(5001, -1)); 
        for(int i=0; i<=9; i++){
            if(i==5){
                continue; 
            }
            ans = (ans+solve(i, 1, arr, n, dp))%mod; 
        }
        return ans; 
    }
};
43742