2025年3月16日 星期日 甲辰(龙)年 月十五 设为首页 加入收藏
rss
您当前的位置:首页 > 计算机 > 编程开发 > 数据结构与算法

程序员的算法趣题Q15: 走楼梯

时间:12-27来源:作者:点击数:43

1. 问题描述

本题来自《程序员的算法趣题》中的第15题。

A和B分别站在楼梯的底部和顶部,A和B同步移动(即每次都是同时移动),A向下走,B向上走,每次可以走的级数为{1,2,3,4},但是两人每次的级数不一定相同。两人同时开始走,求共有多少种“两人最终在同一级碰头”的情况。

在一次移动的中途插肩而过不算在同一级碰头。比如说两个相距1级,A向上走1级,同时B向下走1级,两个人中途肯定在某个瞬间相遇,但是完成这一次移动后,A将停留在B的上一级楼梯上。

有4级楼梯时示例如下:

2. 递推表达式

假设两人在某一时刻相距的级数为N,相向而行走到碰头的可能情况数用f(N)表示。

考虑A向上走Ak级楼梯,而B向上走Bk级楼梯,则(假设两人还没有走过头)此时两人还相距(N-Ak-Bk)级,这是原始的“相距为N”的求解问题的一个子问题,其解记为f(N-Ak-Bk)。对合法的(Ak,Bk)组合所代表的子问题进行遍历求和即可得到f(N),因此可以得到递推表达式如下所示:

初始条件:

“n<0”表示两人错过了在同一级碰头而且已经走过头了,没有碰头,因此返回0

“n=0”表示两人成功地碰头,因此返回1

“n=1”表示两人相距1级,因为最小移动级数为1级,两人已经不可能成功碰头,因此返回0(这个初始条件不是必须的。可以由移动规则加上“n<0”推导出)。

可以用递归的方式(再加上memoization technique)来时求解递推表达式。

当然也可以用动态规划的策略来实现。

3. 代码与测试

以下是递归式求解的代码示例。

  • # -*- coding: utf-8 -*-
  • """
  • Created on Wed Aug 18 09:55:14 2021
  • @author: chenxy
  • """
  • class Solution:
  • def climbingStairs(self, N: int) -> int:
  • """
  • :N: The total number of stairs between the two ends
  • :
  • :ret: return the number of combinations
  • """
  • # Initialization
  • f = N * [0]
  • f[0] = 1
  • f[1] = 0
  • memo = dict()
  • memo[0] = 1
  • memo[1] = 0
  • def recursive(K):
  • if K in memo:
  • return memo[K]
  • rslt = 0
  • for Ak in range(1,min(4,K-1)+1): # range doesn't include the upper bound, hence '+1' is needed here.
  • for Bk in range(1,min(4,K-1)+1):
  • sub = K-(Ak+Bk)
  • if sub >= 0:
  • sub_rslt = recursive(sub)
  • rslt += sub_rslt
  • memo[K] = rslt
  • return rslt
  • return recursive(N)

测试代码及结果如下:

  • if __name__ == '__main__':
  • import time
  • import random
  • sln = Solution()
  • N = 10
  • t1 = time.monotonic()
  • rslt = sln.climbingStairs(N)
  • t2 = time.monotonic()
  • print('N = {0}, rslt = {1}, tCost = {2}'.format(N,rslt,(t2-t1)))
  • N = 100
  • t1 = time.monotonic()
  • rslt = sln.climbingStairs(N)
  • t2 = time.monotonic()
  • print('N = {0}, rslt = {1}, tCost = {2}'.format(N,rslt,(t2-t1)))

N = 10, rslt = 201, tCost = 0.0

N = 100, rslt = 8971901668275006457052051257, tCost = 0.0

方便获取更多学习、工作、生活信息请关注本站微信公众号城东书院 微信服务号城东书院 微信订阅号
推荐内容
相关内容
栏目更新
栏目热门