腾讯面试题：熊出没

01故事起源

故事，要从住在森林里的大熊发现了一个装满苹果的山洞说起...

牛牛码特

13:14

85%

微信(116)

相亲相爱一家熊🐻

我发现一个山洞，里面有好多苹果🍎，看起来很好吃的样子～

不过我们只能从洞口和洞尾拿苹果，我们来比比看谁拿的苹果重量最大吧～

好啊好啊

那我们赶快去山洞吧！

熊熊们山洞之旅遇到的问题，归纳起来就是：给定一个装满苹果的山洞，只能从洞口和洞尾拿苹果，每轮两只熊交替拿，并且只能拿一个，谁拿的苹果总重量最大谁就获胜，那谁会是最终的赢家呢？

02问题剖析

假定山洞里苹果的分布为：1KG，3KG，14KG，7KG。

直觉上来说，是不是我们每轮拿最大的，就一定赢？如果是这种策略，那么大熊第一轮拿7KG，此时的状况就变成了：

这时候很显然，二熊会拿最右边14KG的苹果：

现在山洞里只剩下1KG和3KG两个苹果，无论大熊拿哪一个，它手上苹果总重量，也没二熊的重。难道这是大熊的必输局？

那么，让我们换种拿法，重来一遍。

如果第一轮，大熊选择拿第一个苹果，那此时状态就变成了：

这个时候，二熊只能从3KG、7KG里面选，无论拿哪个，大熊第三轮拿到14KG都能获胜。因此，只要开局拿1KG，大熊就是必胜的。

所以说，每轮选最大这种策略行不通，我们还需要考虑到对后面苹果的影响。

相信经过这个分析，大家已经对题目比较清楚，甚至有点解题思路了吧？别着急，现在我们就一起来看看有哪些解决办法吧。

03花式取苹果

深度优先递归法

我们可以把问题抽象出来，大熊第一轮去取苹果，是否能赢取决于两个因素：一个是取的苹果的重量，另一个是二熊对剩下的进行选择。再仔细一想，二熊面临的问题，其实和大熊开始时是一模一样的。这样思路就很明显了，我们可以用递归的方法去解决问题。

下面这张图，可以帮助我们辅助思考。

我们从最右边往左边看，每一轮都选择当前的最优解，整个流程走下来，就是递归的实际执行流程了。

经过上述分析，代码也很清晰明了：

func CanFistBearWin(nums []int) bool {
    return picker(0, len(nums)-1, nums) >= 0
}

// i, j 表示当前子问题中，山洞左右从哪里开始
func picker(i, j int, nums []int) int {
    if i == j {
        return nums[i]
    }
    head := nums[i] - picker(i+1, j, nums)
    end := nums[j] - picker(i, j-1, nums)
    return max(head, end)
}

记忆化递归法

问题虽然解决了，但是跑了一下测试用例，发现用时100ms以上。这样看来，性能上是不是还有优化空间呢？

可以看到，图上是有重复子问题的，那我们完全可以将子问题的解答记录下来。等到后面再遇到的时候，直接返回结果，而不用再递归下去，这样就可以节约大量时间了。

动态规划法

在上面的分析中，我们已经把问题拆分为子问题，既然是子问题，又可以递归解决，那么就不由地会去想，能不能通过动态规划，递推解决？

依照惯例，我们需要一个dp数组，在上面的分析中不难看出，这个数组应该是二维的，dp[i][j]就表示左边起点为i，右边起点为j的山洞，在先手的情况下，熊熊能拿多少KG的苹果。

既然要用动态规划，那么一定要找到一个公式。我们前面分析过，如果大熊先手，是否能赢取决于两个因素：一个是取的苹果的重量，另一个是二熊对剩下的进行选择。

根据这两个因素，我们可以转化为下列公式：

dp[i][j] = Max(nums[i]-dp[i+1][j], nums[j]-dp[i]dp[j-1])

再结合下面的图来进行推导。我们还是以四个苹果为例，为苹果从左到右编上号。

0号位置对应的dp[0][0]就是其苹果的重量，我们从1号位置开始，对每个位置往前递推：

🍎红苹果配合代码食用更佳：

func CanFistBearWin(nums []int) bool {
    // 提前计算数组长度，避免反复消耗
    length := len(nums)
    dp := make([][]int, length)
    // 子数组初始化
    for i := 0; i < length; i++ {
        dp[i] = make([]int, length)
        // 左右在一个点的情况，取了这个苹果即可
        dp[i][i] = nums[i]
    }
    // j表示山洞右侧位置
    for j := 1; j < length; j++ {
        // i表示山洞左侧位置
        for i := j-1;  i >= 0; i-- {
            head := nums[i] - dp[i+1][j]
            end := nums[j] - dp[i][j-1]
            dp[i][j] = max(head, end)
        }
    }
    return dp[0][length-1] >= 0
}

果不其然，成功拿到了苹果，熊熊开心地跳起了舞

04熊熊复盘

解决此类问题的核心思想，是将从洞两端选择苹果这个问题抽离出来，成为子问题。然后，在此基础上，我们建立了递归解法，根据实际运行的结果，使用记忆化搜索优化，提高了性能。

解决了问题就算完成任务了？我们的目标可是成为一名追求极致的工程师，当然会想还有没有其它解决方案。于是，我们将同一种抽象模型，从递归转换成递推，玩了把动态规划。

换个角度看问题，生命会展现出另一种美。生活中不是缺少美，而是缺少发现。算法也一样，同一个问题，学着用多个角度去思考、解决，你会发现它别样的魅力！

- EOF -

推荐阅读  点击标题可跳转

觉得本文有帮助？请分享给更多人

推荐关注「算法爱好者」，修炼编程内功

点赞和在看就是最大的支持❤️