【腾讯面试题】熊出没
苦逼的码农
共 3633字,需浏览 8分钟
·
2021-07-04 08:53
牛牛码特
13:14
85%
微信(116)
相亲相爱一家熊🐻
我发现一个山洞,里面有好多苹果🍎,看起来很好吃的样子~
不过我们只能从洞口和洞尾拿苹果,我们来比比看谁拿的苹果重量最大吧~
好啊好啊
那我们赶快去山洞吧!
深度优先递归法
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)
}
记忆化递归法
可以看到,图上是有重复子问题的,那我们完全可以将子问题的解答记录下来。等到后面再遇到的时候,直接返回结果,而不用再递归下去,这样就可以节约大量时间了。
动态规划法
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
}
果不其然,成功拿到了苹果,熊熊开心地跳起了舞
评论