前言

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

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

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

讲解试题

动态规划的套路

动态规划（Dynamic Programming，DP）是运筹学的一个分支，是求解决策过程最优化的过程。

动态规划的题目比较多，比如：最长递增子序列问题、最短路径问题、背包问题、资源分配问题等。

动态规划并不是万能的，适用动态规划的问题必须满足最优子结构和无后效性。

• 最优子结构：动态规划问题一定会具备最优子结构，通过子问题的最值得到原问题的最值。
• 无后效性：将各阶段按照一定的次序排列好之后，对于某个给定的阶段状态，它以前各阶段的状态无法直接影响它未来的决策，而只能通过当前的这个状态，换句话说，每个状态都是过去历史的一个完整总结。
• 子问题的重叠性：动态规划的关键在于解决重复问题，问题可以按阶段拆分，然后通过空间换时间的方式减少计算时长。

下面通过斐波那契数列问题详解，了解一下什么是状态转移方程，如何解决重叠子问题。

BM62 斐波那契数列

牛客网入口 BM62 斐波那契数列（简单）

斐波那契数列的定义就是一个标志性的状态转移方程，根据方程我们可以知道：

• fib(1)=1
• fib(2)=1
• fib(3)=fib(3-1)+fib(3-2)=2
• fib(4)=fib(4-1)+fib(4-2)=3
• fib(x)=fib(x-1)+fib(x-2)

而在我们解决其他问题时，也需要按这个思路反向推导 状态转移方程。

为啥叫「状态转移方程」？

其实就是为了听起来高端。你把 f(n) 想做一个状态 n，这个状态 n 是由状态 n - 1 和状态 n - 2 相加转移而来，这就叫状态转移。

1. 递归暴力求解

斐波那契数列的数学形式就是递归的，写成代码就是这样：

def dfs(x):
    if x == 1 or x == 2:
        return 1
    # x > 2
    return dfs(x-1) + dfs(x-2)

这段代码看上去虽然简洁易懂，但是性能低下，不断的进行重复计算，我们应该怎么解决呢？
假设 n = 5，我们画出递归树，如下图：

在递归树中我们可以看出，f(3) 子问题被计算了两次，如果n值很大时子问题被重复计算的次数会更多，这就是动态规划问题的第一个性质：子问题的重叠性。

2. 子问题优化的递归求解

通过上面的分析不难发现，如果我们将之前已经计算的结果保存下来，下一次子问题计算时现在缓存中查找是否有计算过，如果已经计算过直接把答案拿出来用，不要再耗时去计算了，保证相同的子问题只计算一次。

cache = {}

def dfs(x):
    if x == 1 or x == 2:
        return 1

    if x in cache:
        return cache[x]
    else:
        cache[x] = dfs(x - 1) + dfs(x - 2)
        return cache[x]

此时的递归树递归深度减少，实际上，子问题优化的递归算法，就是把一棵存在巨量冗余的递归树通过「剪枝」，改造成了一幅不存在冗余的递归图，极大减少了子问题（即递归图中节点）的个数。

你会发现，上面的两种解法中 return f(n - 1) + f(n - 2) 就是状态转移方程式。可见列出状态转移方程的重要性，它是解决问题的核心。

而且很容易发现，其实状态转移方程直接代表着暴力解法。千万不要看不起暴力解，动态规划问题最困难的就是写出这个暴力解，即状态转移方程。

我们在对比下动态转移方程和暴力解法：

def dfs(x):
    if x == 1 or x == 2:
        return 1
    # x > 2
    return dfs(x-1) + dfs(x-2)

耗时比较