htkb-proconの日記

初心者がPythonで問題解いた記録

桁DP

Educational DP Contest S - Digit Sum 桁DP

めんどくさすぎるイメージを持っていた桁DP、久しぶりに遭遇して解いたら割とソラで書けたのはいいけどTLEで、考察したらそもそも無駄に配列の次元を深くしたりしなくていいんじゃないの??と思ったので書き残してみる。 桁DPの状態遷移はこのように上の桁…