この記事の続きです。ちゃんと想定解のDPで解き直したので、それの解説というか、おぼえがきです。
問題
https://codeforces.com/contest/1341/problem/D
問題概要
7セグがn個並んでいて、点灯状況が与えられる。しかし、k個のセグメントが故障している。
k個の故障箇所を直した時に表現できる可能性のある数値のうちで、最大のものを答えよ。ただし、「故障」とは点灯すべきセグメントが点灯していない状況を指す。（本来消灯すべきセグメントが点灯しているという状況は考慮しない） ただし、いかなる組み合わせでも数値として表現不可能である場合は-1を回答とせよ。
考察
制約（n <= 2000）や問題の性質から察するに、こういうのはだいだいDPで解けそうだとなり、実際解けます。ただし、何も考えずにDP配列を作ったり漸化式を作ると失敗します。（しました）
失敗その1
dp[i][j] = i文字目までにj個のセグメントを修正した時に作れる最大の数値（文字列）
とすればいけそうな気がします。実際いけます（多分）。メモリ空間が無限に与えられていれば！
というわけで、そんな巨大な文字列配列を作るとMLEで死にます。（死にました）
MLEになるコード例 - > Submission #78030083 - Codeforces
失敗その2
ここでわからなくなったので、仕方なくEditorialを開きますと、Let dp[i][j]=true...とか書いてあるので、DP配列はboolで持って遷移可能範囲を先に決めてから、あとで復元すればよいということがわかります。（わかりました）
ここで気をつけないといけないのは、DP配列を埋めるのは後ろから（この問題だと右側から）がよいということです。前から埋めてしまうと、きっちりkを使い切ったかどうかの判断ができなくなる（やりにくくなる？）からです。
前からやろうとして失敗した例 - >Submission #78039757 - Codeforces
完成
というわけで、完成したのがこちらです - >Submission #78041529 - Codeforces
まとめ
メモリ使用量とか、DP配列の構築法とかいろいろ勉強になりました。（今まで知らんかったんかい、というツッコミはさておいて）
