前言

《华为机试真题详解》专栏含牛客网华为专栏、华为面经试题、华为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