象棋中马只能走日， 给你任意一个点（x, y），问你马从左下角走到这个点且只能走k步，问走到这个点的方法数有多少种？ ps: 棋盘是10行9列的

    image.png
    image.png

    1.   public static int ways(int x, int y, int k) {
    2.       return f(x, y, k);
    3.   }
    5. private static int f(int x, int y, int k) {
    6.     if (k == 0) {
    7.         return x == 0 && y == 0 ? 1 : 0;
    8.     }
    9.     if (x < 0 || x > 9 || y < 0 || y > 8) {
    10.         return 0;
    11.     }
    12.     return  f(x - 2, y - 1, k - 1)
    13.         + f(x - 2, y + 1, k - 1)
    14.         + f(x - 1, y + 2, k - 1)
    15.         + f(x + 1, y + 2, k - 1)
    16.         + f(x + 2, y + 1, k - 1)
    17.         + f(x + 2, y - 1, k - 1)
    18.         + f(x + 1, y - 2, k - 1)
    19.         + f(x - 1, y - 2, k - 1);
    21. }

    改动态规划
    image.png

    1.  public static int ways2(int x, int y, int k) {
    2.      int[][][] dp = new int[10][9][k + 1];
    3.      dp[0][0][0] = 1;
    4.      for (int level = 1; level <= k; level++) {
    5.          for (int i = 0; i < 10; i++) {
    6.              for (int j = 0; j < 9; j++) {
    7.                  dp[i][j][level] = getValue(i - 2, j - 1, level - 1, dp)
    8.                      + getValue(i - 2, j + 1, level - 1, dp)
    9.                      + getValue(i - 1, j + 2, level - 1, dp)
    10.                      + getValue(i + 1, j + 2, level - 1, dp)
    11.                      + getValue(i + 2, j + 1, level - 1, dp)
    12.                      + getValue(i + 2, j - 1, level - 1, dp)
    13.                      + getValue(i + 1, j - 2, level - 1, dp)
    14.                      + getValue(i - 1, j - 2, level - 1, dp);
    15.              }
    16.          }
    17.      }
    18.      return dp[x][y][k];
    19.  }
    21. public static int getValue(int x, int y, int k, int[][][] dp) {
    22.     if (x < 0 || x > 9 || y < 0 || y > 8) {
    23.         return 0;
    24.     }
    25.     return dp[x][y][k];
    26. }