【Python】三井住友信託銀行プログラミングコンテスト2019C(DPの使いどころさん)【AtCoder】 - Qiita

※この記事は、DP(動的計画法)の基本中の基本である かえるくん問題2問がとけることを前提としています。 Frog1 Frog2 DPでとけるんだ！！！ と感動した問題がありましたので記事にします。 DPの考え方は知っているけれども、実際の問題と結びつかない！ という人は参考になるかも(ならないかもw) 三井住友信託銀行プログラミングコンテスト2019C Difficulty:205 問題を読んで、bit全探索や6重for文が一瞬頭をよぎりましたがダメそう。 ちなみにDPが思いつかなくても解けます。(記事の最後に別解として載せておきます。) しかしDPが思いつかなかった場合、 たぶん法則性をみつけるのに15分くらいかかる気がします。 レートをあげるには早解きが必須！ DPのメリット DPのいいところは、(DPに限らずの話ですが) 「この問題、DPで解ける！」と気づいた瞬間、ほぼ脳死でコーデ