第一个参数int N，有N个位置1，2，3，4~N，N>1
    第二个参数int S,开始位置，有个机器人停在哪个位置上，是1~N中间的。
    第三个参数int E,是目标位置，从S出发到E
    第四个参数int K，机器人必须走K步，要想从S到达E，有多少种方法？可以随意向左向右走

    1.     public static int ways1(int N, int start, int aim, int K) {
    2.         if (N < 2 || start < 1 || start > N || aim < 1 || aim > N || K < 1) {
    3.             return -1;
    4.         }
    5.         return process1(N,aim,start,K );
    6.     }
    8.     // 有哪些位置？1~N  固定参数
    9.     // 最终的目标是aim， 固定参数
    10.     // 机器人当前来到的位置是cur，可变参数
    11.     // 机器人还有rest步需要去走， 可变参数 
    12.     // 返回：机器人从cur出发，走过rest步之后，最终停在aim的方法数，是多少？
    13.     // 当可变参数确定，返回值确定
    16.     // 暴力递归版本  O(2^k)
    17.     public static int process1(int N, int aim, int cur, int rest ) {
    18.         if (rest == 0) { // 如果已经不需要走了，走完了！ basecase
    19.             return cur == aim ? 1 : 0; // 剩0步到达aim就是一种方法
    20.         }
    21.         // 还有路可以走
    22.         // rest>0 ,来到1，必须1→2，还剩rest-1。
    23.         if (cur == 1) { // 1 -> 2
    24.             return process1(N ,aim, 2, rest - 1 );
    25.         }
    26.         // 来到N,没有选择只能N-1后退，  还剩rest-1
    27.         if (cur == N) { // N-1 <- N
    28.             return process1(N ,aim, N - 1, rest - 1 );
    29.         }
    30.         // 机器人来到中间位置，有两种选择，往左迈一步，往右迈一步。
    31.         return process1(N ,aim,cur - 1, rest - 1) + process1( N ,aim, cur + 1, rest - 1);
    32.     }
    34.     // 记忆化搜索，搞定可变参数组合    O(KxN)
    35.     public static int ways2(int N, int start, int aim, int K) {
    36.         if (N < 2 || start < 1 || start > N || aim < 1 || aim > N || K < 1) {
    37.             return -1;
    38.         }
    39.         // 开多大分析可变参数范围，0~K,K+1,  1~N,N+1,0位置是无法到达的
    40.         int[][] dp = new int[N + 1][K + 1];
    41.         // 初始化都置成-1，不是-1就代表计算过，直接返回。
    42.         for (int i = 0; i <= N; i++) {
    43.             for (int j = 0; j <= K; j++) {
    44.                 dp[i][j] = -1;
    45.             }
    46.         }
    47.         // dp就是缓存表
    48.         // dp[cur][rest] == -1 -> process1(cur, rest)之前没算过！
    49.         // dp[cur][rest] != -1 -> process1(cur, rest)之前算过！返回值，dp[cur][rest]
    50.         // N+1 * K+1
    51.         return process2(start, K, aim, N, dp);
    52.     }
    54.     // cur 范: 1 ~ N
    55.     // rest 范：0 ~ K
    56.     public static int process2(int cur, int rest, int aim, int N, int[][] dp) {
    57.         if (dp[cur][rest] != -1) { // 状态计算过返回
    58.             return dp[cur][rest];
    59.         }
    60.         // 之前没算过！缓存没命中 尝试
    61.         if (rest == 0) {
    62.             dp[rest][cur] = cur == aim ? 1 : 0; // 记忆
    63.             return dp[cur][rest];
    64.         }
    66.         // rest >0 有路可走
    67.         if (cur == 1) {
    68.             dp[rest][cur] = process2(2, rest - 1, aim, N, dp);// 记忆
    69.         } else if (cur == N) {
    70.             dp[rest][cur] = process2(N - 1, rest - 1, aim, N, dp);// 记忆
    71.         } else {
    72.             dp[rest][cur] = process2(cur - 1, rest - 1, aim, N, dp) + process2(cur + 1, rest - 1, aim, N, dp);// 记忆
    73.         }
    75.         return dp[cur][rest];
    77.     }
    79.     // DP  改递归代码从格子取值
    80.     public static int ways3(int N, int start, int aim, int K) {
    81.         if (N < 2 || start < 1 || start > N || aim < 1 || aim > N || K < 1) {
    82.             return -1;
    83.         }
    84.         int[][] dp = new int[N + 1][K + 1];
    85.         dp[aim][0] = 1;
    86.         for (int rest = 1; rest <= K; rest++) {
    87.             dp[1][rest] = dp[2][rest - 1];
    88.             for (int cur = 2; cur < N; cur++) {
    89.                 dp[cur][rest] = dp[cur - 1][rest - 1] + dp[cur + 1][rest - 1];
    90.             }
    91.             dp[N][rest] = dp[N - 1][rest - 1];
    92.         }
    93.         return dp[start][K];
    94.     }