全探索のdpでの実装をしたい

Question

前提・実現したいこと

AOJのALDS1_5_Aの問題をdpで解こうと思い実装したのですが、vectorのサイズオーバフローのエラーが出ました。なぜ出るのか全く分からないので、教えていただきたいです。問題の内容は、入力4行目の各数について、入力2行目の数をいくつか足し合わせて作ることができるか判定せよ、というものです。

発生している問題・エラーメッセージ

terminate called after throwing an instance of 'std::out_of_range'
  what():  vector::_M_range_check: __n (which is 18446744073709551597) >= this->size() (which is 2005)
Aborted (core dumped)

入力例

5
1 5 7 10 21
4
2 4 17 8

期待される出力例

no
no
yes
yes

該当のソースコード

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

#define MAX 2005
vector<vector<int>> dp(25, vector<int> (MAX, -1)); // dp配列

int n, q;
vector<int> a(MAX);

int solve(int i, int m) {
  if(dp.at(i).at(m) != -1) return dp.at(i).at(m); // 該当の部分が計算済みならそれを返す

  if(m == 0) { // m == 0なら可能
    dp.at(i).at(m) = 1;
  }else if(i >= n) { // i >= nなら不可
    dp.at(i).at(m) = 0;
  }else if(solve(i + 1, m) == 1) { 
    dp.at(i).at(m) = 1;
  }else if(solve(i + 1, m - a.at(i)) == 1) {
    dp.at(i).at(m) = 1;
  }else{
    dp.at(i).at(m) = 0;
  }
  return dp.at(i).at(m);
}

int main() {
  cin >> n;
  for(int i = 0; i < n; i++) cin >> a.at(i);
  cin >> q;
  for(int i = 0; i < q; i++) {
    int m;
    cin >> m;
    if(solve(0, m)) cout << "yes" << endl;
    else cout << "no" << endl;
  }
  return 0;
}

Answer 1

  }else if(solve(i + 1, m - a.at(i)) == 1) {

ここで、mがa.at(i)より小さいと、solveの引数mがマイナスになります。
そうすると、solveの先頭でマイナスのインデックスにアクセスしようとしてエラーになります。

---

追記

mがマイナスならメモ化もせずに返るようにすれば修正できます。

 int solve(int i, int m) {
+  if(m < 0) return 0;
   if(dp.at(i).at(m) != -1) return dp.at(i).at(m); // 該当の部分が計算済みならそれを返す

mがマイナスの時にorimで登録するのは誤りです。
今回のコードだと実行順の関係で問題が発生することはありませんが、
solve(i+1,m-a.at(i),orim)側を先に呼び出すようになっていたら、正常動作しないパターンが出てきます。

2
4 3
1
3

Comments

[PC_breakman]

原因をくださってありがとうございます。無事解決できました。

[PC_breakman]

追記ありがとうございます。
mが書き換えられてしまうからということでしょうか。

[actorbug]

コメントからすると、何か勘違いされているように思います。
リンク先の問題(英語版)にsolveの呼び出し階層の図が書いてあると思いますが、
私が提示した「正常動作しないパターン」で同じ図を書いてみてください。
そして、どの位置でmがマイナスになるか、そこでdp.at(i).at(orim)に0を書き込むのが本当に正しいか
確認してみてもらえませんか。

Answer 2

下記のように、多少強引ですが、再帰処理によって時々刻々変化するmの値をもう一つ引数として保持しておくことで解決できました。ほかに何かいい方法があったら是非教えてください。

int solve(int i, int m, int orim) {
  if(m >= 0 && dp.at(i).at(m) != -1) return dp.at(i).at(m);
  
  if(m == 0) {
    return dp.at(i).at(m) = 1;
  }else if(i >= n || m < 0) {
    if(m < 0) m = orim;
    return dp.at(i).at(m) = 0;
  }
  int res = solve(i + 1, m, orim) || solve(i + 1, m - a.at(i), orim);
  if(res) {
    dp.at(i).at(m) = 1;
  }else{
    dp.at(i).at(m) = 0;
  }
  return dp.at(i).at(m);
}

int main() {
  cin >> n;
  for(int i = 0; i < n; i++) cin >> a.at(i);
  cin >> q;
  for(int i = 0; i < q; i++) {
    int m;
    cin >> m;
    if(solve(0, m, m)) cout << "yes" << endl;
    else cout << "no" << endl;
  }
  return 0;
}