【华为机试真题详解】小兔子繁殖详解

前言

《华为机试真题详解》专栏含牛客网华为专栏、华为面经试题、华为OD机试真题。

如果您在准备华为的面试，期间有想了解的可以私信我，我会尽可能帮您解答，也可以给您一些建议！

本文解法非最优解（即非性能最优）。

讲解试题 题目详情DP2 跳台阶一只青蛙一次可以跳上1级台阶，也可以跳上2级。求该青蛙跳上一个 n 级的台阶总共有多少种跳法（先后次序不同算不同的结果）。【机试题】小兔子繁殖有一只兔子，从出生后第3个月起每个月都生一只兔子，小兔子长到第三个月后每个月又生一只兔子，假如兔子都不死，问到达 M 月时有几只兔子。 如何写一个递归函数

看过上一篇文章的同学可能也发现了，递归函数是求解动态规划问题的一个很好的方法，那我们要如何写一个递归函数呢？

如果一个函数在执行过程中，直接或者间接的调用自己，我们称之为递归函数。

递归的应用场景，链表操作、二叉树操作、排列组合问题和动态规划问题等，他们有一个特点就是随着递归深度的增加，问题规模在不断减小。

比如我们在学校汇报演出的大礼堂里，你想知道你在第几排时会怎么做呢？ 方案一： 走到第一排再一排一排的数到你所在的这一排。 方案二： 问前一排的同学是第几排，在他的基础上+1就是当前的排数，前一排也不清楚的话重复问他的前一排，直到问到第一排的同学。

这就是一个简单的递归函数：

def dfs(n):
    if n == 1:
        return 1
    return dfs(n-1) + 1

递归问题难实现，很重要的一个问题是如何确认递归的终止条件，我们在跳台阶问题深入学习

DP2 跳台阶

牛客网入口 DP2 跳台阶（简单）

一只青蛙一次可以跳上1级台阶，也可以跳上2级。求该青蛙跳上一个 n 级的台阶总共有多少种跳法（先后次序不同算不同的结果）。

分析问题时，我们考虑从问题规模小的情况入手，

当只有一级台阶时只能跳一级，也就只有一种跳法； 当只有二级台阶时可以一次能跳二级，也可以分两次跳一级，就有二种跳法； 当只有三级台阶时可以先跳二级再跳一级，先跳一级再跳两级，也可以分三次跳都一级，就有三种跳法；

再想一下： 从三层楼开始： 不管是有几层楼梯，都是要选择先跳一层还是先跳两层 假如我先跳一层，子问题就变成了f(n-1)个跳法的问题， 假如我先跳两层，子问题就成了f(n-2)个跳法的问题。 往下层子模块叠加

转换下公式: f(1) = 1 f(2) = 2 f(3) = f(3-1) + f(3-2) f(4) = f(4-1) + f(4-2) f(n) = f(n-1) + f(n-2)

想到这里时，递归函数的必要条件就都有了

def dfs(n):
    if n == 1:
        return 1
    if n == 2:
        return 2
    return dfs(n-1) + dfs(n-2)

到这步就完成了平时常提到的暴力破解，也就是没有考虑重复计算问题；

这时我们按在上一节提到的优化方式进行优化。

cache = {}
def dfs(n):
    if n in cache:
        return cache[n]
    elif n == 1:
        return 1
    elif n == 2:
        return 2
    cache[n] = dfs(n-1) + dfs(n-2)
    return cache[n]

下面拿一道华为真题练习一下。

小兔子繁殖

【华为机试真题 Python实现】小兔子繁殖

有一只兔子，从出生后第3个月起每个月都生一只兔子，小兔子长到第三个月后每个月又生一只兔子，假如兔子都不死，问到达 M 月时有几只兔子。

例如： 4 月，有 2 只， 5 月有 3 只，。。。 7 月有 6 只。

转换下公式: f(1) = 1 f(2) = 1 f(3) = 1 f(4) = f(3) + f(1) f(5) = f(4) + f(2) f(6) = f(5) + f(3) f(7) = f(6) + f(4)

状态转移方程* f(n) = 1 # n 3

暴力递归

def dfs(n):
    if n