本题来自《程序员的算法趣题》中的第15题。
A和B分别站在楼梯的底部和顶部,A和B同步移动(即每次都是同时移动),A向下走,B向上走,每次可以走的级数为{1,2,3,4},但是两人每次的级数不一定相同。两人同时开始走,求共有多少种“两人最终在同一级碰头”的情况。
在一次移动的中途插肩而过不算在同一级碰头。比如说两个相距1级,A向上走1级,同时B向下走1级,两个人中途肯定在某个瞬间相遇,但是完成这一次移动后,A将停留在B的上一级楼梯上。
有4级楼梯时示例如下:
假设两人在某一时刻相距的级数为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)来时求解递推表达式。
当然也可以用动态规划的策略来实现。
以下是递归式求解的代码示例。
- # -*- 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