henoc https://blog.hatena.ne.jp/henoc/ henoc’s blog https://henoc.hatenadiary.jp/ leetcode Pythonで書いてあった解法を見て書きました arr1のある位置までで構成できる単調増加列について、最後尾の値をkey, その場合の置換処理の最小回数をvalueとしたdpを考える。それをHashMapでdpとする。 初期値として dp[-1] = 0 を入れておく。 あるarr1上の位置iに対して arr1[i]があるkeyより真に大きい場合、遷移は２通り： arr2を使用せずそのまま単調増加列に追加する arr2からkeyを超える最小の要素を使い、単調増加列に追加する そうでない場合、遷移は１通り： arr2からkeyを超える最小の要素を使い、単調増加列に追加する use std::cm… 190 <iframe src="https://hatenablog-parts.com/embed?url=https%3A%2F%2Fhenoc.hatenadiary.jp%2Fentry%2F2019%2F09%2F08%2F171141" title="Weekly Contest 153 : 1187. Make Array Strictly Increasing - henoc’s blog" class="embed-card embed-blogcard" scrolling="no" frameborder="0" style="display: block; width: 100%; height: 190px; max-width: 500px; margin: 10px 0px;"></iframe> Hatena Blog https://hatena.blog 2019-09-08 17:11:41 rich https://henoc.hatenadiary.jp/entry/2019/09/08/171141 1.0 100%