【腾讯面试题】熊出没

苦逼的码农

共 3633字,需浏览 8分钟

 ·

2021-07-04 08:53

周五来了,即将快乐周末,今天就给大家分享一道有趣的算法题,希望能给大家带来一个好心情~

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

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

换个角度看问题,生命会展现出另一种美。生活中不是缺少美,而是缺少发现。算法也一样,同一个问题,学着用多个角度去思考、解决,你会发现它别样的魅力!
浏览 40
点赞
评论
收藏
分享

手机扫一扫分享

分享
举报
评论
图片
表情
推荐
点赞
评论
收藏
分享

手机扫一扫分享

分享
举报