初始化大型vector<vector<int>>触发std::bad_alloc错误求助

嘿，这个问题我之前做股票DP题的时候也踩过坑！std::bad_alloc说白了就是你的程序要的内存太多，系统给不起了，咱们来聊聊问题根源和解决办法：

为什么会出这个错？ #

你初始化的二维vector是vector<vector<int>> result(k, vector<int> (prices.size() + 1, 0))，咱们算下内存需求：

• 每个int占4字节（多数平台），总元素数是k * (prices.size() + 1)
• 如果k是个很大的数（比如上万），或者prices的长度特别长（比如几十万），两者相乘的总字节数会直接超出进程能申请的内存上限，系统自然就拒绝分配了，抛出bad_alloc。

针对性解决办法 #

1. 优化DP状态空间（核心方案） #

股票买卖的DP问题根本不需要完整的二维数组！以你这个最多k次交易的场景来说，result[i][j]表示第i次交易、第j天的最大利润，但我们只需要前一轮的交易状态就能计算当前轮，完全可以把二维数组压缩成两个一维数组，甚至更小：

比如用两个一维数组分别记录「第i次交易买入后的最大利润」和「第i次交易卖出后的最大利润」，空间复杂度直接从O(k*n)降到O(k)，代码示例：

class Solution {
public:
    int maxProfit(int k, vector<int>& prices) {
        int n = prices.size();
        if (n == 0) return 0;
        
        // 极端情况：k大到相当于无限次交易
        // 因为最多只能完成n/2次有效交易（每次买卖占2天）
        if (k >= n / 2) {
            int totalProfit = 0;
            for (int i = 1; i < n; ++i) {
                if (prices[i] > prices[i-1]) {
                    totalProfit += prices[i] - prices[i-1];
                }
            }
            return totalProfit;
        }
        
        // 用两个一维数组保存状态：buy[i]是第i次买入后的最大利润，sell[i]是第i次卖出后的最大利润
        vector<int> buy(k + 1, INT_MIN);
        vector<int> sell(k + 1, 0);
        
        for (int price : prices) {
            for (int i = 1; i <= k; ++i) {
                buy[i] = max(buy[i], sell[i-1] - price);
                sell[i] = max(sell[i], buy[i] + price);
            }
        }
        
        return sell[k];
    }
};

2. 提前过滤极端场景 #

• 如果prices是空数组，直接返回0，没必要初始化任何数组；
• 当k >= n/2时，直接用贪心算法处理，既省空间又省时间，还能避免申请超大内存。

3. 检查k的输入合理性 #

如果k是用户传入的参数，要确认它的取值范围。比如题目有没有限制k的最大值？如果没有，就必须用上面的极端情况处理，防止k被传入一个离谱的大数（比如1e9）。

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