DP - 棋盘走法的可能性

问题一

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;
    }
}