問題一

0  1  2              // 0->5,7; 1-> 6,8; 2->3, 7
3  4  5              // 3->2,8,9; 4 ->沒有走法 ; 5->0,6,9;
6  7  8              // 6->1,5; 7-> 0,2; 8-> 1, 3;
.  9  .              // 9->3,5;

給定以上2d Array作為棋盤，起始位置為任意位置，移動方式為走 L型（0可以到5和7，1可以到6，8， 3可以到2和8）。問給定步數k，有幾種走法。

可以理解為數字出現的可能性是固定的，數字只能走到固定的幾個位置且固定的幾個位置也只能到這個數字。所以k次只要疊加就可以了。

動態(tài)解法

時間復雜度O(k+n(1))，空間復雜度為O(n(1))，這里n固定為10個數字，

class Solution {
    public int findSolution(int k) {
        int[] dp = new int[10];
        Arrays.fill(map,1);
        for(int i = 1; i < k; i++) {
            int[] temp = new int[10];
            temp[0] = dp[7]+dp[5];  
            temp[1] = dp[6]+dp[8];
            temp[2] = dp[3]+dp[7];
            temp[3] = dp[2]+dp[8]+dp[9];
            temp[4] = 0;     
            temp[5] = dp[0]+dp[6]+dp[9];
            temp[6] = dp[1]+dp[5];
            temp[7] = dp[0]+dp[2];
            temp[8] = dp[3]+dp[1];
            temp[9] = dp[3]+dp[5];
            dp = temp;
        }
        int res = 0;
        for(int each : dp) res += each;
        return res;
    }
}