时间戳

首页 > 解决方案 > 子集 dp 问题导致分段错误

subset - 子集 dp 问题导致分段错误

问题描述

给定一组数字，检查它是否可以划分为两个子集，使得两个子集中的元素之和相同。我在 C++（g++ 5.4）中遇到了分段错误，这个问题。这是我在 C++ 中提交我的解决方案的地方

https://practice.geeksforgeeks.org/problems/subset-sum-problem/0

我正在检查数组是否可以分成总和相等的两部分。所以我只是检查是否存在总和等于数组总和一半的子集

我已经用动态编程实现了以下逻辑

令 dp[i][j] 表示是或否，总和为 j 的子集是否可以与范围 [0, i]（包括）内的元素形成，其中 i 是基于 0 的索引。我对这个传统问题没有做任何新的事情。但是我遇到了分段错误。该程序为小型测试用例提供正确的输出。我犯了什么错误

我没有使用任何评论，因为我没有做任何新的事情。希望可以理解。

#include <iostream>
#include <bits/stdc++.h>
#include<cstdio>
#define ll long long int
using namespace std;


bool isVowel(char c){
    return c == 'a' || c == 'e' || c == 'i' || c == 'o' || c == 'u';
}

bool isLower(char c){
    return 97 <= c && c <= 122;
}


int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    cout << setprecision(10);

    ll t, n;
    cin >> t;
    while (t--) {
        cin >> n;
        ll a[n];
        ll sum = 0;

        for (ll i = 0; i < n; i++) {
            cin >> a[i];
            sum += a[i];
        }

        if (sum % 2) {
            cout << "NO" << '\n';
            continue;
        }

        sum /= 2;
        ll dp[n][sum + 1];
        for (ll i = 0; i < n; i++) {
            for(ll j = 0; j < sum + 1; j++) {
                dp[i][j] = 0;
            }
        }

        for (ll i = 0; i < n; i++) {
            dp[i][a[i]] = 1;
            dp[i][0] = 1;
        }


        for (ll i = 1; i < n; i++) {
            for (ll j = 1; j < sum + 1; j++){
                if (j - a[i] > 0) {
                    dp[i][j] = dp[i - 1][j - a[i]];
                }

                dp[i][j] |= dp[i - 1][j];
            }
        }

        cout << (dp[n - 1][sum] ? "YES" : "NO") << '\n';

    }
}

标签： subsetdynamic-programming

解决方案

分段错误是由于 

ll dp[n][sum + 1];

即使约束说1 <= N<= 100, 0 <= arr[i]<= 1000，使用的测试用例可能要大得多，所以ll dp[n][sum + 1]最终会采取一些严肃的态度堆栈内存，使用 

bool dp[n][sum + 1];

它应该可以正常工作。

附带说明，避免随机使用 ll，根据约束使用它们。

推荐阅读