给定一个整数数组 a ，每个元素表示一个位置上的数值。要求从数组中选择若干个元素，使得任意两个被 选择的元素在原数组中都不相邻，并且所选元素的总和最大。函数 choose(a) 返回能够得到的最大总和，则横线 处应填写（ ） def choose(a): if not a: return 0 n = len(a) if n == 1: return a[0] dp = [0] * n dp[0] = a[0] dp[1] = max(a[0], a[1]) for i in range(2, n): dp[i] = ___________________________ return dp[-1]
A：dp[i - 1] + a[i]
B：max(dp[i - 1], dp[i - 2] + a[i])
C：max(dp[i - 2], a[i])
D：dp[i - 1] + dp[i - 2]
正确答案：B
答案解析
定义 dp[i] 表示从前 i+1 个元素中选择不相邻元素所能获得的最大和。初始状态为 dp[0] = a[0]，dp[1] = max(a[0], a[1])。对于位置 i（i ≥ 2），决策是是否选择 a[i]。若不选 a[i]，则最大和为 dp[i-1]；若选择 a[i]，则不能选 a[i-1]，最大和为 dp[i-2] + a[i]。因此 dp[i] 应取两者较大值。
试卷来源：202606 CCF-GESP编程能力等级认证Python六级真题