求以数组首元素开头且总权重≤k的最长子序列的DP递推式

嘿，这个问题用动态规划确实是绝佳选择，而且因为题目里k和数组元素Ai的取值范围都很小（最多到50），我们可以设计出一个效率极高的DP方案，完全能搞定n=1e5的大规模输入。让我一步步给你拆解思路：

核心DP状态定义 #

我们定义dp[j][v]表示：总权重恰好为j，且子序列最后一个元素的值为v时，子序列的最长长度。

这里的关键是利用约束条件缩小状态空间：

• j的范围是0到k（因为总权重不能超过k），共k+1种可能；
• v的范围是0到50（因为Ai ≤50），共51种可能；

所以整个DP表的大小只有(k+1)*51，最多是51*51=2601个状态——这在大规模输入下完全不会有内存或性能压力。

初始状态设置 #

因为子序列必须以数组第一个元素开头，所以初始时只有：
dp[0][A[0]] = 1（总权重为0，最后一个元素是A[0]，子序列长度为1）。

其他所有dp[j][v]我们可以初始化为-∞（表示该状态不可达，后续计算时不会干扰最大值的选取）。

递推过程 #

遍历数组从第二个元素开始（每个元素记为num），对于每个元素，我们有两种选择：选或不选它。

1. 不选当前元素：此时DP状态保持不变，我们可以先复制当前的DP表到一个临时表new_dp中。
2. 选当前元素：对于每个可达的状态dp[j][v]（即dp[j][v] != -∞），计算加入num后的新权重：
   new_j = j + abs(v - num)
   如果new_j ≤k，说明这个新状态是合法的，我们就更新new_dp[new_j][num]为max(new_dp[new_j][num], dp[j][v]+1)——也就是取当前状态长度加1后的最大值。

最后，把new_dp赋值给dp，继续处理下一个元素。

示例验证 #

拿你给出的例子来走一遍流程：

• 输入：n=4, k=5, A=[1,2,50,6]
• 初始状态：dp[0][1] =1，其他为-∞
• 处理元素2：
  • 计算new_j=0+|1-2|=1 ≤5，所以new_dp[1][2] =1+1=2
  • 此时dp中保留dp[0][1]=1和dp[1][2]=2
• 处理元素50：
  • 无论从dp[0][1]还是dp[1][2]计算，new_j都会超过5，所以无法更新状态，dp保持不变
• 处理元素6：
  • 从dp[0][1]计算：new_j=0+|1-6|=5 ≤5，new_dp[5][6] =1+1=2
  • 从dp[1][2]计算：new_j=1+|2-6|=5 ≤5，new_dp[5][6] =max(2,2+1)=3
• 最终遍历所有dp[j][v]，最大值是3，和示例结果一致。

伪代码实现 #

def longest_valid_subsequence(A, k):
    n = len(A)
    max_ai = 50
    # 初始化DP表，用-∞表示不可达状态
    dp = [[float('-inf')] * (max_ai + 1) for _ in range(k + 1)]
    dp[0][A[0]] = 1
    
    for num in A[1:]:
        # 复制当前DP状态，对应不选当前元素的情况
        new_dp = [row.copy() for row in dp]
        for j in range(k + 1):
            for v in range(max_ai + 1):
                if dp[j][v] == float('-inf'):
                    continue
                added_weight = abs(v - num)
                new_j = j + added_weight
                if new_j > k:
                    continue
                # 更新新状态的最长长度
                if new_dp[new_j][num] < dp[j][v] + 1:
                    new_dp[new_j][num] = dp[j][v] + 1
        dp = new_dp
    
    # 遍历所有状态找最大值
    max_length = 0
    for j in range(k + 1):
        for v in range(max_ai + 1):
            max_length = max(max_length, dp[j][v])
    return max_length

# 测试示例
A = [1,2,50,6]
k =5
print(longest_valid_subsequence(A,k)) # 输出3

复杂度分析 #

• 时间复杂度：O(n * k * max_ai)，其中n是数组长度，k≤50，max_ai≤50。对于n=1e5，总操作次数约为1e5 *50*50=2.5e7，这在大多数编程语言中都能轻松通过。
• 空间复杂度：O(k * max_ai)，仅需存储一个51x51的二维数组，空间消耗极小。

内容的提问来源于stack exchange，提问作者Raokfc Rdkf