良い\(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)\)となり十分に間に合う。以下は実装例。
#include<bits/stdc++.h>
using namespace std;
#define fs first
#define sc second
#define mp make_pair
#define pb push_back
#define eb emplace_back
#define ALL(A) A.begin(),A.end()
#define RALL(A) A.rbegin(),A.rend()
typedef long long LL;
typedef pair<double,double> P;
const LL mod=1e9+7;
const LL LINF=1LL<<62;
const LL INF=1<<30;
int main(){
int N;
cin >> N;
int dp[N+1];
for(int i=0;i<N+1;i++){
dp[i]=INF;
}
dp[0]=0;
for(int i=0;i<N;i++){
int s=1;
while(1){
if(i+s>N) break;
dp[i+s]=min(dp[i+s],dp[i]+1);
s*=6;
}
s=1;
while(1){
if(i+s>N) break;
dp[i+s]=min(dp[i+s],dp[i]+1);
s*=9;
}
}
cout << dp[N] << endl;
return 0;
}
今回の問題は貪欲法でも解けるみたいですね（公式の解答）