猴子爬山问题

问题

一只顽猴儿在一座有 n 级台阶的山上爬山，假设猴子上山一步可跳1级台阶或3级台阶。试求猴子上山有多少种不同爬法。

分析

这一问题实际上是一个整数有序可重复拆分问题，通过递归思想求解：

f(n) –> n 级台阶的爬山总方法数
考虑在猴子到达最后一个台阶时，其所处位置在 n-1 台阶处或n-3 台阶处，故有 f(n) = f(n-1) + f(n-3)
因 n>0 , 故：
- n=1 或 n=2 , f(1) = f(2) = 1
- n = 3 , f(3) = 2

程序设计

python 实现

#!/usr/bin/env python3

import functools


@functools.lru_cache()
def recursion_count(n: "int, and n > 0"):
    if n == 1 or n == 2:
        return 1
    elif n == 3:
        return 2
    elif n > 3:
        return recursion_count(n-1) + recursion_count(n-3)


if __name__ == "__main__":
    a = recursion_count(50)
    print(a)  # 122106097

functools.lru_cache 为python中一个缓存装饰器，其作用可以直接将函数或类方法的结果缓存住，后续调用则直接返回缓存的结果。

原型如下：

@functools.lru_cache(maxsize=None, typed=False)

maxsize –> 最多缓存的次数，如果为 None，则无限制，设置为 2 的幂时，性能最佳

typed=True –> 不同参数类型的调用将分别缓存，例如 f(3) 和 f(3.0)。(注意，在 functools32 中没有此参数)

LRU (Least Recently Used，最近最少使用) 算法是一种缓存淘汰策略。其根据数据的历史访问记录来进行淘汰，核心思想是，“如果数据最近被访问过，那么将来被访问的几率也更高”。该算法最初为操作系统中一种内存管理的页面置换算法，主要用于找出内存中较久时间没有使用的内存块，将其移出内存从而为新数据提供空间。