章末問題 4.6回答例 でメモ参照のインデックスが負数になる可能性がある

[ichihara-3]

章末問題4.6の解答例で、w - a[i - 1]が負数になる可能性があり、その場合次の再起実行時の memoへの参照が負数になります。
そのため、想定外の書き換えや、a[i-1]の値が大きいときにはvectorの領域外への参照により結果が不定となる現象が発生し得ます。

book_algorithm_solution/solutions/chap04.md

Line 201 in bf4af1b

if (func(i - 1, w - a[i - 1], a)) return memo[i][w] = 1;

例えば、以下のような入力は必ずNoになるはずですが、私の実行環境ではYesが出力されることがありました。

20
5
7 9 21 23 25 27 29 31 33 35 37 39 41 43 45 47 49 51 53 55

解決策としては、func()内で w<0 のときfalseで返却してしまうなどが考えられると思います