程序员的算法趣题：Q15 走楼梯（Java版）

题目说明

A从底部上楼梯时，B从该楼梯的顶部往下走。
每次不一定只走 1 级，最多可以一次跳过 3 级（即直接前进 4 级）。
但无论走多少级，1 次移动所需时间不变。
两人同时开始走，求共有多少种“两人最终同时停在同一级”的情况
（假设楼梯宽度足够，可以相互错开，不会撞上。另外，同时到达同一级时视为结束）。

思路1

1.A上楼，一次走1~4级台阶；B下楼，一次走1~4级台阶
2.用双重循环罗列出A和B这一步所走的台阶数的所有可能性
3.当A所在的台阶级数比B所在的台阶级数大时，结束递归（A和B已经错过了）
4.A和B处在同一级时，正确答案+1

代码1

public static void main(String[] args) {// A的起点：0级台阶// B的起点：10级台阶// 每一步可以走的最大台阶数：4System.out.println(move(0, 10, 4));
}

/*** A从a出发上楼；B从b出发下楼。* 统计同时到达同一级台阶的走法有多少种* @param a     A所处的级数* @param b     B所处的级数* @param max   一步最多移动的级数* @return      正确答案的个数*/
public static int move(int a, int b, int max) {if (a > b) return 0;if (a == b) return 1; // 到达相同台阶，正确答案+1int count = 0;// 双重循环罗列了A和B这一步的所有可能性for (int i = 1; i <= max; i++) {     // 这一步：A上楼走的台阶数for (int j = 1; j <= max; j++) { // 这一步：B下楼走的台阶数count += move(a + i, b - j, max);}}return count;
}

代码1优化版（时间性能）

此种递归方式随着递归层级变多，耗时较大。（实测30层台阶，耗时5300ms+。优化后耗时10ms~20ms，粗略计算时间性能提升200+倍）
可以采用“内存化”的方法，把计算过的数据存入map中，下次计算同样的递归时，直接从map中获取结果，避免重复计算，进而提示时间效率。

// 键：a,b 值：move(a,b)的结果（说明：a和b表示具体的数字）
public static Map<String,Integer> hmap = new HashMap<>();
public static void main(String[] args) {long start = System.currentTimeMillis(); // 当前系统时间 ms值System.out.println(move(0, 30, 4));long end = System.currentTimeMillis(); // 当前系统时间 ms值System.out.println((end-start)+" ms"); // 30级 5425 ms ==> 10 ms
}

public static int move(int a, int b, int max) {if (a > b) return 0;if (a == b) return 1;// 如果map中已经计算过该结果，则直接获取即可if(hmap.containsKey(a+","+b)) return hmap.get(a+","+b);int count = 0;for (int i = 1; i <= max; i++) {for (int j = 1; j <= max; j++) {count += move(a + i, b - j, max);}}// 将本次计算结果存入map，下次需要重复计算时直接去map中拿结果hmap.put(a+","+b, count); return count;
}

思路2

1.A走“偶数”步到达B的情况就是我们想要的结果（“偶数”步意味着一定存在某一级台阶到达A、B两点的步数相同）
2.动态规划：第n步时，站在t级台阶的情况数量，取决于前一步（第n-1步）时(t-4)到(t-1)四级台阶的情况数量之和

示意图

补充说明：空白区域的值为0

代码2

public static void main(String[] args) {int N = 10;     // 最高台阶级数（B所在的台阶级数）int STEPS = 4;  // 一步最多走几级台阶int[] arr = new int[N + 1];     // [0,N] 算上辅助计算的起点（A点），共N+1个元素arr[0] = 1;     // 辅助计算的值。可以理解为：走0步时，到达起点（A点）的情况只有这一种int count = 0;  // 统计正确答案的数量// i表示走的步数，一共N级台阶，最大不超过N步// 举例：当i=3时，arr[10]的值表示走3步到达第10级台阶（B点）有几种走法，从示意图可知有6种走法for(int i = 1; i <= N ; i ++){// 计算走了i步时，到达各级台阶的走法有多少种for(int j = N; j >= i; j --){   // 从最后一级依次往前计算（后面的值是前面4个元素的旧值，所以需要从后往前计算）arr[j] = 0;                 // 清除当前位置的旧值for(int k = 1; k <= STEPS; k ++){     // 表示(j-1) ~ (j-4) 前4个元素arr[j] += j-k < 0 ? 0 : arr[j-k]; // 如果下标为负，避免下标越界，直接赋值为0}}arr[i-1] = 0; // 清除之前位置的旧值（走i步，则最少站在i级台阶上，之前台阶上的数据要清空）System.out.println(Arrays.toString(arr)); // 查看每一步到达各级台阶的情况if(i%2 == 0) count += arr[N]; // 偶数步到达B级台阶（B点）的步数要计入正确答案，可以参考示意图}System.out.println("count = " + count); // 201
}

结果

201