为什么要全局声明向量并在运行时异常的局部函数中进行初始化？

Question

我正在在线平台上解决一些回溯问题。这是我的代码

vector<vector<int> > dp;     // STATEMENT 1
//vector<vector<int> > dp(1000, vector<int>(1000,0)); // STATEMENT 2
void initialize_dp(string stg)
{
    int n = stg.length();
    for(int i = 0; i < n; i++)
    {
        dp.push_back(vector<int>(n,0)); // STATEMENT 3
    }
    for(int i = 0 ;i <n ;i++)
        dp[i][i] = 1;
    for(int len = 2; len <= n; len++)
    {
        for(int i = 0, j = i+len-1; i < n && j < n; i++, j++)
        {
            if(stg[i] == stg[j])
            {   
                if(len == 2)
                    dp[i][j] = 1;
                else
                    dp[i][j] = dp[i+1][j-1];
            }
            else 
                dp[i][j] = 0;
        }
    }
}
void solve(string &A, int n, int k, vector<vector<string> >&result, vector<string> temp)
{
    if(k == n)
    {
        result.push_back(temp);
        return;
    }
    int i,j;
    i = k;
    for(int j = k; j < n; j++)
    {
        if(dp[i][j] == 1)
        {
            temp.push_back(A.substr(i, j-i+1));
            solve(A, n, j+1, result, temp);
            temp.pop_back();
        }
    }
}
vector<vector<string> > startFunction(string A) {
    int n = A.length();
    initialize_dp(A);
    vector<vector<string> > result;
    vector<string> temp;
    solve(A, n,0, result, temp);
    return result;
}

在代码中，我全局声明了vector<vector<int> >，当我声明使用STATEMENT2时，它可以正常工作。但是，当我使用STATEMENT1和内部函数initialize_dp（string stg）对其进行声明时，我在STATEMENT3中初始化了此全局向量，然后它在提交时显示了运行时异常。但是，在我的本地计算机上，它可以很好地处理在线平台上失败的输入。不知道该怎么做。

Answer 1

带有此语句：

vector<vector<int> > dp;

向量的大小为0，因为它为空。您可以使用dp.size()进行检查。

因此，此循环将不会运行以填充矢量：

int n = stg.length();
for(int i = 0; i < n; i++)
{
    dp.push_back(vector<int>(n,0)); // STATEMENT 3
}

因为这里n为0。

并且，当您尝试在此循环中访问向量的内存时，由于未初始化，将导致Undefined Behavior：

for(int i = 0 ;i <n ;i++)
    dp[i][i] = 1;           // invalid access here

带有声明

vector<vector<int> > dp(1000, vector<int>(1000,0));

向量是用1000个元素构造和初始化的。因此，内存访问将是有效的并且可以工作。

[请注意，在第二种情况下，矢量已经初始化，因此第一个循环是多余的。而且，如果将内部向量初始化为1，则也不需要第二个循环。

这里是一个5x5矩阵（live）的示例：

#include<iostream>
#include<vector>

int main()
{
    std::vector<std::vector<int>> dp ( 5, std::vector<int>(5, 1) );

    for ( int i {0}; i < dp.size(); ++i )
    {
        for ( int j {0}; j < dp[i].size(); ++j )
        {
            std::cout << dp[i][j] << ' ';
        }
        std::cout << '\n';
    }

    return 0;
}

输出：

1 1 1 1 1 
1 1 1 1 1 
1 1 1 1 1 
1 1 1 1 1 
1 1 1 1 1

使用C ++ 11的range-for循环，会更整洁。

示例（live）：

#include<iostream>
#include<vector>

int main()
{
    std::vector<std::vector<int>> dp ( 5, std::vector<int>(5, 1) );

    for ( const auto& row : dp )
    {
        for ( const auto& col : row )
        {
            std::cout << col << ' ';
        }
        std::cout << '\n';
    }

    return 0;
}