題目連結：
題目意譯：
西洋棋騎士的移動方式很特別，它可以往鉛直方向移動兩格加上水平方向移動一格，或是往水平方向移動兩格加上鉛直方向移動一格（兩者都會形成一個 L 形）。下圖為一個騎士所有可能的移動方式：
我們有一個西洋棋騎士以及一台手機（如下圖），該騎士可以能站在數字鍵上方（即藍色格子）。
給定一個整數 n，回傳我們可以藉由騎士來撥長度 n 的電話號碼之總方法數。
你被允許在最一開始將騎士放在任一數字鍵上，而接著你可以執行 n - 1 次移動來撥出一個長度為 n 的電話號碼。每次移動都必須是一個合法的騎士移動。
由於答案可能很大，將其模 10 ^ 9 + 7 後再回傳。
限制：
1 ≦ n ≦ 5000
範例測資：
範例 1：
輸入： n = 1
輸出： 10
解釋： 我們需要撥出一個長度 1 的數字，所以將騎士放在任意一個數字鍵上即可。
範例 2：
輸入： n = 2
輸出： 20
解釋： 所有我們能撥出的數字為 [04, 06, 16, 18, 27, 29, 34, 38, 40, 43, 49, 60, 61, 67, 72, 76, 81, 83, 92, 94]
範例 3：
輸入： n = 3131
輸出： 136006598
解釋： 請注意模運算。
解題思維：
可以看到：
0 的前面可以接 4 、 6；
1 的前面可以接 6 、 8；
2 的前面可以接 7 、 9；
3 的前面可以接 4 、 8；
4 的前面可以接 0 、 3 、 9；
6 的前面可以接 0 、 1 、 7；
7 的前面可以接 2 、 6；
8 的前面可以接 1 、 3；
9 的前面可以接 2 、 4；
因此我們可以定義一個二維陣列 D，其中 D[i][j] 代表著有多少電話號碼滿足長度為 i 且以數字 j（0 ≦ j ≦ 9）結尾，可以看到其遞迴式為：
D[1][j] = 1，對於任意 j
D[i][j] = sum(D[i - 1][j'])，其中 sum 為加總之操作而 j' 為可以接在 j 前面的數字。
而答案為 D[n][1] + D[n][2] + …… + D[n][9]。
此次分享到此為止，如有任何更加簡潔的想法或是有說明不清楚之地方，也煩請各位大大撥冗討論。
