How to Win the Apple‑Picking Game: Recursive and DP Strategies Explained

Story Origin

The tale starts with a bear discovering a cave full of delicious apples and deciding to compete with another bear by taking apples from the cave's entrance or exit.

Problem Statement

Given a cave containing apples of various weights, two bears alternately take one apple from either the leftmost or rightmost end. Each bear aims to maximize the total weight of apples they collect. Determine which bear can guarantee a larger total weight.

Why Greedy Fails

Choosing the heaviest available apple each turn does not always lead to victory. For example, with apple weights 1 kg, 3 kg, 14 kg, 7 kg , if the first bear greedily takes 7 kg, the second bear can take 14 kg and secure the win.

However, if the first bear starts by taking the 1 kg apple, the remaining configuration forces the second bear into a suboptimal choice, allowing the first bear to capture the 14 kg apple later and win.

Depth‑First Recursive Solution

The problem can be expressed recursively. Let picker(i, j) return the maximum net weight the current player can achieve from the sub‑array nums[i…j]. The recurrence is:

func CanFirstBearWin(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)
    if head > end {
        return head
    }
    return end
}

Memoized Recursion

Because the same sub‑problems are solved repeatedly, caching their results (memoization) eliminates redundant work and reduces the running time from exponential to polynomial.

Dynamic Programming Solution

Using a two‑dimensional DP table dp[i][j] that stores the maximum net gain for the sub‑array i…j, the transition mirrors the recursive formula:

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

Implementation in Go:

func CanFirstBearWin(nums []int) bool {
    n := len(nums)
    dp := make([][]int, n)
    for i := 0; i < n; i++ {
        dp[i] = make([]int, n)
        dp[i][i] = nums[i]
    }
    for j := 1; j < n; j++ {
        for i := j - 1; i >= 0; i-- {
            head := nums[i] - dp[i+1][j]
            end := nums[j] - dp[i][j-1]
            if head > end {
                dp[i][j] = head
            } else {
                dp[i][j] = end
            }
        }
    }
    return dp[0][n-1] >= 0
}

Bear Recap

The core idea is to abstract the "pick from both ends" operation into sub‑problems and solve them via recursion, memoization, or bottom‑up DP. Each method provides a clear path to determine whether the first bear can secure a win.

Exploring multiple perspectives on the same algorithmic challenge reveals deeper insights and strengthens problem‑solving skills.