AOJ DPL_1 A Combinatiorial Coin Changing Problem

問題

Coin Changing Problem

解法

DPのプラクティスのセットのところの問題ですので当然DP。普通にDPを組むと何枚でも使用できるってのkを使用枚数の上限としてO(nmk)ってなるので間に合わない。たぶん正答率が低いのはこれでTLEが出てるからかと。

dp[i+1][j]の計算においてk(k>=1)個選ぶ場合は、dp[i+1][j-d[j]]の計算でk-1個選んだときの計算がされてるのでkに関するループを減らせる。

O(nm)で解けるようになり間に合う。

心臓に悪いコード

int dp[MAX_M+1][MAX_N+1];
int n, m, d[MAX_M];

int main(){
  scanf("%d%d", &n, &m);
  rep(i, m) scanf("%d", d+i);

  rep(i, MAX_M+1) rep(j, MAX_N+1) dp[i][j] = INF;
  dp[0][0] = 0;
  rep(i, m){
    rep(j, n+1){
      dp[i+1][j] = min(dp[i][j], dp[i+1][j-d[i]] + 1);
    }
  }

  printf("%d\n", dp[m][n]);
  return 0;
}