🎯 最长非连续子序列和为给定值（Longest Subsequence with Sum K）

📘 题目描述

给定一个长度为 n 的整数数组 a[1..n]，以及一个目标整数 K，请你找出一个​最长的非连续子序列​，使得该子序列的和恰好等于 K。

注意：

• 子序列中的元素顺序不变；
• 子序列中的元素可以​跳过中间项​，不要求连续；
• 若不存在这样的子序列，输出 0。

📥 输入格式

• 第一行两个整数：n 和 K。
• 第二行 n 个整数：数组 a[1..n]。

📤 输出格式

• 一个整数，表示和为 K 的最长非连续子序列的长度。如果无法满足，则输出 0。

💡 输入输出样例

输入样例 #1

5 15
2 3 7 8 10

输出样例 #1

3

解释：最长子序列 [2, 3, 10]，总和为 15，长度为 3。

输入样例 #2

5 9
1 2 3 4 5

输出样例 #2

3

解释：最长子序列 [1, 3, 5]。

🚧 边界样例

🧠 解题思路（动态规划）

我们定义一个二维 dp[i][s] 表示：

• 用前 i 个数能否凑出和为 s 的子序列；
• 值为 -1 表示无法凑出；
• 否则存储能凑出该和的​最长子序列的长度​。

⚙ 状态转移方程

dp[i][s] = max(
    dp[i-1][s],                  // 不选 a[i]
    dp[i-1][s - a[i]] + 1        // 选 a[i]
)

• 初始状态：dp[0][0] = 0（选 0 个数凑出和为 0）；
• 答案是 dp[n][K]；
• 注意空间和时间都为 O(n × K)，需要用 memset 或 vector 初始化。