周五来了，即将快乐周末，今天就给大家分享一道有趣的算法题，希望能给大家带来一个好心情～
故事，要从住在森林里的大熊发现了一个装满苹果的山洞说起...
我发现一个山洞，里面有好多苹果🍎，看起来很好吃的样子～
不过我们只能从洞口和洞尾拿苹果，我们来比比看谁拿的苹果重量最大吧～
熊熊们山洞之旅遇到的问题，归纳起来就是：给定一个装满苹果的山洞，只能从洞口和洞尾拿苹果，每轮两只熊交替拿，并且只能拿一个，谁拿的苹果总重量最大谁就获胜，那谁会是最终的赢家呢？
假定山洞里苹果的分布为：1KG，3KG，14KG，7KG。
直觉上来说，是不是我们每轮拿最大的，就一定赢？如果是这种策略，那么大熊第一轮拿7KG，此时的状况就变成了：
现在山洞里只剩下1KG和3KG两个苹果，无论大熊拿哪一个，它手上苹果总重量，也没二熊的重。难道这是大熊的必输局？
如果第一轮，大熊选择拿第一个苹果，那此时状态就变成了：
这个时候，二熊只能从3KG、7KG里面选，无论拿哪个，大熊第三轮拿到14KG都能获胜。因此，只要开局拿1KG，大熊就是必胜的。
所以说，每轮选最大这种策略行不通，我们还需要考虑到对后面苹果的影响。
相信经过这个分析，大家已经对题目比较清楚，甚至有点解题思路了吧？别着急，现在我们就一起来看看有哪些解决办法吧。
深度优先递归法
我们可以把问题抽象出来，大熊第一轮去取苹果，是否能赢取决于两个因素：一个是取的苹果的重量，另一个是二熊对剩下的进行选择。再仔细一想，二熊面临的问题，其实和大熊开始时是一模一样的。这样思路就很明显了，我们可以用递归的方法去解决问题。我们从最右边往左边看，每一轮都选择当前的最优解，整个流程走下来，就是递归的实际执行流程了。func CanFistBearWin(nums []int) bool { return picker(0, len(nums)-1, nums) >= 0}
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] } for j := 1; j < length; j++ { 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}
果不其然，成功拿到了苹果，熊熊开心地跳起了舞
解决此类问题的核心思想，是将从洞两端选择苹果这个问题抽离出来，成为子问题。然后，在此基础上，我们建立了递归解法，根据实际运行的结果，使用记忆化搜索优化，提高了性能。解决了问题就算完成任务了？我们的目标可是成为一名追求极致的工程师，当然会想还有没有其它解决方案。于是，我们将同一种抽象模型，从递归转换成递推，玩了把动态规划。换个角度看问题，生命会展现出另一种美。生活中不是缺少美，而是缺少发现。算法也一样，同一个问题，学着用多个角度去思考、解决，你会发现它别样的魅力！
