子序列最大权重DP问题中含a0时为何取a0+Y/2

基础题设 #

• 实数序列a0, a1, …, an-1的权重计算规则为：a0 + a1/2 + a2/2² + … + an-1/2^(n-1)
• 子序列定义：删除原序列部分元素、保持剩余元素相对顺序不变得到的序列
• 符号约定：
  • X：序列a0,a1,…,an-1的子序列最大可能权重
  • Y：序列a1,a2,…,an-1的子序列最大可能权重
• 题目给出四个选项：
  • (A) max(Y, a0+Y)
  • (B) max(Y, a0+Y/2)
  • (C) max(Y, a0+2Y)
  • (D) a0+Y/2
• 官方正确答案为B。

官方动态规划思路 #

求解X时可以拆成两个完全覆盖所有可能、且互斥的决策分支：

1. 最优子序列不包含a0：此时问题等价于直接求a1到an-1的最大子序列权重，结果就是Y。
2. 最优子序列包含a0：此时最大权重为a0 + Y/2，因为Y对应的最优子序列接在a0之后时，每个元素的权重都会额外除以2，而Y本身已经是a1到an-1区间能取到的最优值。
   最终X为两个分支的最大值，即max(Y, a0+Y/2)，对应选项B。

核心疑问澄清 #

很多人第一次推导会困惑：为什么包含a0的分支不是a0+Y，而是要给Y除以2？
问题的核心是：每个元素的权重不是固定值，完全由它在最终选中的子序列里的位置决定。
举个最简单的具象例子：当n=2，序列为[a0, a1]时，Y是a1单独作为序列的最大子序列权重，也就是选a1时的权重a1。如果我们选了a0作为子序列的第一个元素，再选a1的话，a1在子序列里排第二位，对应的权重就变成了a1/2，而不是原来的a1，这部分的总贡献就是Y/2，不是Y。
推广到一般情况也是一样：当你把a0放在子序列的第一位，后面所有从a1~an-1里选出来的元素，在最终子序列里的排位都会比它们作为a1开头序列的子序列时往后顺移1位，每一项的分母都多乘一个2，整体权重自然就变成原来的1/2。这时候你只要照搬取Y时选中的子序列接在a0后面，就能拿到Y/2的最大值——毕竟Y已经是a1~an-1区间能凑出的最高权重，哪怕整体折半，也没有其他选法能拿到更高的值。

错写成a0+Y的本质是默认了后面元素的权重固定不变，忽略了选a0之后，后续所有元素的权重都会因为位置后移被稀释一半，这就是这个误区的来源。

内容的提问来源于stack exchange，提问作者Nisarg Devani