AOJ 2607 - Invest Master

Invest Master
提出コード
一見どっから手を付ければいいか悩みますが、わかるとすごくスッキリします。
手数料が何もないので、毎日株をすべて一度手放し換金するものとします。とくに2日以上同じ株を持ち続けるメリットはありません。
そこで、i日目でうまく株を買い、i+1日目の手持ちを最大にすることを考えます。
動的計画法を利用します。
ナップサック問題に帰着することができます。 重さ制限 →i日目の手持ちの最大値
荷物の重さ→i日目の株の値段
価値 →i+1日目の株の値段
として、価値を最大、つまりi+1日目の手持ちを最大にしていきます。
個数制限がないナップサック問題になります。
i-1日目に、重さがjになるように株を買ったときの、i日目の手持ちの最大は
dp[i][j] = max(dp[i-1][j],dp[i-1][j-p[i-1][k]] + p[i][k])
です。kは銘柄の番号になります。配列の添え字が0未満になるものは無視します。
あとはこれをd日間繰り返すのですが、一つだけ注意が必要になります。
手持ちのお金に対して、株価を買わずに持ち続けておくという選択肢が存在します。
これは、i日目とi+1日目の株価が常に同じような銘柄を追加することで、同じ操作をすることができます。