问题一
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次只要叠加就可以了。
动态解法
时间复杂度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;
}
}
