2944. Minimum Number of Coins for Fruits | 1709

 1class Solution:
 2    def minimumCoins(self, prices: List[int]) -> int:
 3        # intuition: backtrack
 4        # 1. purchase this fruit
 5        # 2. take for free (if possible)
 6        # need memoization
 7
 8        # how to turn backtrack into DP:
 9        # Backtracking = “try choices from a position”
10        # DP = “notice you revisit the same situation; cache it”
11        # So the whole game is: define “same situation” = your **state**.
12
13        n = len(prices)
14
15        @lru_cache(None)
16        def dfs(pos, free_end):
17            if pos > n:  # OB
18                return 0
19            if pos > free_end:  # have to pay
20                return prices[pos - 1] + dfs(pos + 1, max(2 * pos, free_end))
21            else:  # can take free
22                return min(
23                    dfs(pos + 1, free_end),
24                    prices[pos - 1] + dfs(pos + 1, max(2 * pos, free_end)),
25                )
26
27        return dfs(0, 0)