アルゴ式のテスターに選ばれました（2日目）

別に毎日更新しようと思っているわけではありませんが，たまたま気が向いたので今日も書きます．

進捗

今日は動的計画法のQ2-1～Q2-4までをやりました．２次元の動的計画法の前半部分です．昨日取り組んだ内容と比べるとやや時間がかかりましたが何とかＡＣできました．

感想

Q2-1，Q2-2は良いとして，Q2-3で少し悩みました．以前もやったことがあるような問題だし，DPっぽいなと思うのですがなかなか手が付きません．今回の問題を通して，配列dpの取り方（置き方？）がよく理解できていなかったということを自覚しました． Q2-3では，

dp[i]がi日目の報酬の最大値

のようにすればよいのかな？と漠然と考えていました．ただ，もしi日目に仕事0を行っていたとするとi+1日目には仕事0は行うことができません．でもi+1日目に仕事0を行った方が報酬の最大値が大きくなる可能性があるということくらいは僕でもわかります．今まではここまで考えて，うーん，うーんとうなって終わりだったような気がします．

今日はこのあともう少し考えてdp[i][j]は，i日目に仕事jをやったときの報酬の最大値とすれば良さそうであると気づくことができました．なぜ気づくことができたのかと言われれば２次元動的計画法の問題だよと教えてもらっていたからな気がします．

あと，Q2-4の解説を読んで，初めて「配るDP」と「貰うDP」の意味が分かりました．今までピンと来てませんでした．けんちょん本もよんだりQiitaの記事も読んだりしましたが，なんで今までピンと来ていなかったのでしょうか．

おわりに

毎日こんなにたくさんの文章を書くのは無理なので続けられるペースでやります（継続できる範囲で）．明日はきっと更新しません．