# 0935. Knight Dialer
###### tags: `Leetcode` `Medium` `Dynamic Programming`
Link: https://leetcode.com/problems/knight-dialer/
## 思路 $O(N)$ $O(1)$
动态规划
因为在到达每个点之后，能到的下一个点是固定的，因此每多一步，就可以通过上次到达各个点的路径数算出来多一步之后到达每个点的路径数
## Code

class Solution {
    public int knightDialer(int n) {
        int[][] map = new int[][]{{4,6},{6,8},{7,9},{4,8},{3,9,0},{},{1,7,0},{2,6},{1,3},{2,4}};
        int[][] dp = new int[10][n+1];
        int mod = 1000000007;
        for(int i = 0;i < 10;i++){
            dp[i][1] = 1;
        }
        for(int i = 0;i < n;i++){
            for(int j = 0;j < 10;j++){
                for(int next:map[j]){
                    dp[next][i+1] += dp[j][i]%mod;
                    dp[next][i+1] %= mod;
                }
            }
        }
        int ans = 0;
        for(int i = 0;i < 10;i++){
            ans = (ans + dp[i][n]%mod)%mod;
        }
        return ans;
    }
}

优化空间之后
因为dp的值不一定是从小到大或者从大到小改的，所以需要另建一个array存新的值，再在最后把新array的值给旧的array

class Solution {
    public int knightDialer(int n) {
        int[][] map = new int[][]{{4,6},{6,8},{7,9},{4,8},{3,9,0},{},{1,7,0},{2,6},{1,3},{2,4}};
        int[] dp = new int[10];
        int mod = 1000000007;
        for(int i = 0;i < 10;i++){
            dp[i] = 1;
        }
        
        
        for(int i = 1;i < n;i++){
            int[] nextDP = new int[10];
            for(int j = 0;j < 10;j++){
                for(int next:map[j]){
                    nextDP[next] += dp[j]%mod;
                    nextDP[next] %= mod;
                }
            }
            dp = nextDP;
        }
        int ans = 0;
        for(int i = 0;i < 10;i++){
            ans = (ans + dp[i]%mod)%mod;
        }
        return ans;
    }
}