2212. Maximum Points in an Archery Competition[背包问题 最优方案]

https://leetcode.com/problems/maximum-points-in-an-archery-competition/
经典的背包问题，但是要求输出方案，因此还是要注意一下

题目解答

class Solution:
    def maximumBobPoints(self, n: int, a: List[int]) -> List[int]:
        @cache
        def dp(i, k):
            if i <= 0:
                return 0
            if k < a[i] + 1:
                return dp(i - 1, k)
            return max(i + dp(i - 1, k - a[i] - 1), dp(i - 1, k))
        res = [0] * len(a)
        k = n
        for i in range(len(a) - 1, 0, -1):
            if dp(i, k) != dp(i - 1, k):
                res[i] = a[i] + 1
                k -= res[i]
        res[0] += k
        return res

题目分析

没有什么特别好说的：

• 经典0-1背包的转移方程
• 边界条件的判断

方案的输出值得注意一下，可以通过值直接对比是否选择了当前方案：dp(i, k) != dp(i - 1, k)，依次更新就能得到所有的选择情况了。