为什么DeepSeek火之后，人们想到的是大量裁员而不是实行上三休四？

今天给大家带来一道算法题——带限制的子序列和。

题目大概是这样的：给定一个整数数组 arr 和一个数值 k，要求你找到所有满足以下条件的子序列和：

• 子序列的和要小于或等于 k。
• 子序列的元素顺序不能改变。

别小看这个题目，虽然问题看起来比较直白，但实际中可能需要一些巧妙的技巧来高效地解决。我们来分析一下，如何从技术角度一步步攻克这道题。

首先，传统的方式就是考虑所有可能的子序列。你会想到枚举所有子序列，并判断其和是否小于 k，然后输出符合条件的结果。这个方法似乎没什么问题，但我们来看看性能怎么样。

如果我们用递归+回溯的方式来生成所有子序列，其时间复杂度大概是 O(2^n)，也就是所有子序列的数量。对于一个数组大小为 n 的情况，枚举所有子序列的复杂度就直接爆炸了，尤其是当数组的长度大于 20 时，性能就非常差。

那怎么办呢？一个聪明的优化方法就是动态规划（DP）。这里我们可以将问题转化为一个背包问题来求解。这种方式的核心思想就是利用历史计算结果来避免重复计算，提高效率。

我们可以通过动态规划来记录每一组子序列的和，并只保留那些和小于或等于 k 的子序列。具体来说，我们定义一个数组 dp，其中 dp[i] 表示和为 i 的子序列数目。

接下来，我们就可以用动态规划来逐步构建答案。每当我们遍历到一个新元素 arr[i] 时，考虑将它加到已知的子序列中，并更新 dp 数组。这种方式通过不断更新子序列的和，避免了重复计算，从而大大提高了效率。

这里给出一个简单的 Java 代码实现：

public class SubsequenceSum {
    public static int maxSubsequenceSum(int[] arr, int k) {
        int n = arr.length;
        // dp数组，dp[i] 表示和为i的子序列是否存在
        boolean[] dp = new boolean[k + 1];
        dp[0] = true; // 和为0的子序列是存在的（空子序列）
        // 遍历数组中的每个元素
        for (int num : arr) {
            // 遍历当前dp数组，倒序更新
            for (int j = k; j >= num; j--) {
                // 如果dp[j-num]为真，说明加上num后可以构成新的子序列和
                dp[j] = dp[j] || dp[j - num];
            }
        }
        // 统计所有小于等于k的子序列和
        int result = 0;
        for (int i = 0; i <= k; i++) {
            if (dp[i]) {
                result++;
            }
        }
        return result;
    }
    public static void main(String[] args) {
        int[] arr = {3, 34, 4, 12, 5, 2};
        int k = 10;
        System.out.println("The number of subsequences with sum <= " + k + " is: " + maxSubsequenceSum(arr, k));
    }
}

这段代码首先定义了一个布尔数组 dp，其大小为 k+1，用于记录每一个可能的子序列和是否出现。然后我们通过遍历数组中的元素，逐步更新 dp 数组，确保所有合法的子序列和都能被考虑到。最后，我们统计出所有小于等于 k 的子序列和，得出最终结果。

值得注意的是，动态规划的这个做法让我们能够避免枚举所有子序列，极大地减少了时间复杂度，从原来的 O(2^n) 降到了 O(n * k)，这对于大部分问题来说已经是非常高效了。

当然，优化的过程中总会有一些小细节需要注意。例如，在更新 dp 数组时，必须要倒序遍历，因为如果顺序更新的话，会在同一轮迭代中出现错误的状态更新。简单说，就是会“污染”当前状态，导致结果不对。