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

内容导读

互联网集市收集整理的这篇技术教程文章主要介绍了程序员的算法趣题：Q15 走楼梯（Java版），小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含3643字，纯文字阅读大概需要6分钟。

内容图文

题目说明

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级台阶
    // 每一步可以走的最大台阶数：4
    System.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; // 到达相同台阶，正确答案+1

    int 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

内容总结

以上是互联网集市为您收集整理的程序员的算法趣题：Q15 走楼梯（Java版）全部内容，希望文章能够帮你解决程序员的算法趣题：Q15 走楼梯（Java版）所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。

内容备注

版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。

内容手机端

---