Comments良い\(DP\)の問題が出題されたので取り上げてみる。https://abc099.contest.atcoder.jp/tasks/abc099_c問題概要は「一回の取り出しでは、\(1\)円か\(6^{k}\)円か\(9^{k}\)円を取り出すことが出来る時、\(N\)円を取り出すのに必要な最小回数を求めよ」というもの。\(DP\)はいくつかの状態に問題を分割して、部分問題に持ち込むというのが基本。その為、\(DP\)を使う問題では、\(dp\)をどの様に定めるのかが非常に重要になってくる。\(dp\)を定めた後は、\(dp[i]\)が求まっているなら他の\(dp\)の値を求めるのにどう使うことができるのか(\(dp\)の遷移)を考える。\(dp[i]:=i円を取り出すのに必要な取り出し回数の最小値\)このように\(dp\)を定めると答えは\(dp[N]\)になる。実際の遷移について考えていく。\(dp[i]\)が求まっているとすると、\(i\)円を取り出すのに必要な最小回数が求まっているということなので、\(i+6^{k}\)円と\(i+9^{k}\)円は\(dp[i]+1\)回で作ることができる。\(dp[i+6^{k}],dp[i+9^{k}]\)の値よりも\(dp[i]+1\)の方が小さかったら値を更新するという事を繰り返していけば必ず最小回数を求める事ができる。\(dp[0]\)からボトムアップ式に\(dp[i]\)まで求めていくことで遷移は尽くされるので\(dp[i]\)からの遷移を考える時には\(dp[i]\)は求まっている。これを数式で表すと\(dp[i+6^{k}]=min(dp[i+6^{k}],dp[i]+1)\)\(dp[i+9^{k}]=min(dp[i+9^{k}],dp[i]+1)\)\(min\)を使うので、\(dp\)は大きい値で初期化をしておく必要がある。\(dp[0]\)は\(0\)で初期化しておく。この解法の計算量は\(O(NlogN)\)となり十分に間に合う。コメントをキャンセルメールアドレスが公開されることはありません。