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

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