Double Increasing Series动态规划递推式推导原理解析

首先明确动态规划状态的定义，这是理解递推逻辑的前提：

• DP(i, j) 代表：所有元素为不超过i的正整数、长度为j、满足「前序元素值 ≤ 相邻后序元素值1/2」约束的合法序列总数。

所有符合DP(i,j)统计范围的序列，可以不重不漏分成两类，两类数量相加即为总序列数：

1. 序列中完全不包含数值i
   这类序列的所有元素取值上限实际为i-1，且长度仍为j、满足题目的序列约束，因此数量直接等于DP(i-1, j)，也就是递推式的第一项。
2. 序列中包含数值i
   根据题目的约束，序列中靠后的元素值至少是前一个元素的2倍，整个序列严格递增，因此数值i作为当前取值上限下的最大值，必然出现在序列的最后一位。
   当最后一位固定为i时，前面长度为j-1的前缀子序列需要满足两个要求：一是自身符合题目的序列约束，二是前缀的最后一个元素（即整个序列的倒数第二位）必须满足 ≤ i/2——由于前缀本身的递增属性，前缀所有元素自然都不会超过这个值，因此前缀的合法总数就是取值上限为floor(i/2)、长度为j-1的合法序列数，即DP(floor(i/2), j-1)，也就是递推式的第二项。

递推边界说明 #

• 当j=1时，长度为1的序列不存在相邻元素约束，所有1~i的正整数都可以单独构成合法序列，因此DP(i, 1) = i
• 当i=0时，没有可选的正整数，对任意j≥1，都有DP(0, j) = 0
• 可以提前剪枝：长度为j的合法序列最小的末尾值是2^{(j-1)（对应序列1,2,4,...,2}(j-1)），如果2^(j-1) > A，直接返回0即可，不存在合法序列。

简单验证样例 #

比如计算i=4、j=2的情况：
按递推式DP(4,2) = DP(3,2) + DP(2,1)

• 计算得DP(3,2)=2，对应序列[1,2]、[1,3]
• DP(2,1)=2，对应最后一位固定为4时，前缀可选1、2，即序列[1,4]、[2,4]
• 总共有4个合法序列，和手动枚举结果一致。

内容的提问来源于stack exchange，提问作者Ayush Agarwal