何があったか

競技プログラミングの勉強でdpのコードを書いていたときにSegmentation fault: 11というエラーが出ました。
原因がわからず結構悩んだので記事にしておきたいと思います。

実行環境

OS: macOS
言語: C++
コンパイラ: g++

問題が起きたコード

コンパイル時にはエラーにならず、実行時にエラー文が出力されました。

問題のコード

# include<bits/stdc++.h>
using namespace std;

int main(){
  int n, W;
  int dp[1010][10000];
  int value[1010], weight[1010];
  cin >> n >> W;

  //dp初期値設定
  for(int w = 0; w <= W; i++){
    dp[0][i] = 0;
  }
  //value, weight入力
  for(int i = 0; i < n; i++){
    cin >> weight[i] >> value[i];
  }
  //wまでの最大値
  for(int i = 0; i < n; i++){
    for(int w = 0; w <= W; w++){
      if(w >= weight[i]){
        dp[i+1][w] = max(dp[i][w-weight[i]] + value[i], dp[i][w]);
      }
      else{
        dp[i+1][w] = dp[i][w];
      }
    }
  }
  cout << dp[n][W] << endl;
  return 0;
}

今回は、上記のコードを実行したところエラーが出ました。
ちなみにこのコードは@drkenさんの典型的な DP (動的計画法) のパターンを整理 Part 1 ～ナップサック DP 編～を参考にさせていただきました。とても参考になるのでおすすめです。

セグメンテーションフォルトとは

セグメンテーションフォルトについて少し説明しておきます。
ウィキペディアのセグメンテーション違反には、

セグメンテーション違反（英語: segmentation fault）とは、ソフトウェアの実行時のフォールト状態（あるいはフォールト条件）の一種であり、ソフトウェアがアクセス禁止とされているメモリ上のエリアにアクセスしようとしたり、メモリ上の位置ごとに設定されているルールに違反してメモリにアクセスしようとするときに起こるものである。略してセグフォールト（英: segfault）とも。

とあります。
要するに、アクセスできないメモリの領域に対してアクセスしようとすると、セグメンテーションフォルトが起こります。

今回のコードでは

C++では、配列を関数内（ローカル変数）で宣言するとスタック領域にデータが入れられ、関数外（グローバル変数）で宣言すると~~ヒープ領域~~静的領域にデータが入れられるらしいです。
このため、関数内では大きな配列を宣言してはならないようです（スタック領域はOSに決められたサイズしか確保されないため。）。
先ほど載せたコードでは、関数内で宣言された配列のサイズがスタック領域のサイズより大きかったため、セグメンテーションフォルトが起こったようです。
配列の宣言を関数外で行ったところセグメンテーションフォルトは起きませんでした。
一応、変更後のコードを載せておきます。

変更後のコード

# include<bits/stdc++.h>
using namespace std;

int n, W;
int dp[1010][10000];
int value[1010], weight[1010];

int main(){
  cin >> n >> W;

  //dp初期値設定
  for(int w = 0; w <= W; i++){
    dp[0][i] = 0;
  }
  //value, weight入力
  for(int i = 0; i < n; i++){
    cin >> weight[i] >> value[i];
  }
  //wまでの最大値
  for(int i = 0; i < n; i++){
    for(int w = 0; w <= W; w++){
      if(w >= weight[i]){
        dp[i+1][w] = max(dp[i][w-weight[i]] + value[i], dp[i][w]);
      }
      else{
        dp[i+1][w] = dp[i][w];
      }
    }
  }
  cout << dp[n][W] << endl;
  return 0;
}

関数内でのstatic変数も、グローバル変数と同じように静的領域に入れられるので、以下のように関数内でstatic変数を定義することでも、解決できるようです。
static int dp[1010][10000];

まとめ

今まで何度かセグメンテーションフォルトに悩まされていて、その度に調べていた気がするのでいい機会になったかと思います。
今回の原因を調べる中で、自分のメモリ領域に関する知識不足を感じたので、今後そちらの方についても勉強していきたいと思っています。