日記

のみろぐ

主に競プロ日記です

コイン問題

考察

  • 状態変数を考える
  • dp[i円の最小枚数]でいけそう。50000円がMaxだから制約的にも行けそう
  • 次に遷移を考える
  • dp[i] ← dp[i-c[j]] + 1みたいな感じで行けそう。計算量も$O(nm)$で余裕がある。最大で$106$ステップだし

解法

  • dp[i円の最小枚数]という状態を持つ
  • dp[i] ← dp[i - c[j]] + 1という遷移を行う

コード

#include <bits/stdc++.h>
using namespace std;

#define int long long

const int INF = 1e15;

int dp[55555];
int c[22];

int n, m;

signed main() {
  cin >> n >> m;
  for (int i = 0; i < m; i++) {
    cin >> c[i];
  }

  fill(dp, dp+n+5, INF);
  dp[0] = 0;
  for (int i = 0; i <= n; i++) {
    for (int j = 0; j < m; j++) {
      if (i - c[j] >= 0) {
        dp[i] = min(dp[i], dp[i-c[j]] + 1);
      }
    }
  }

  cout << dp[n] << endl;

  return 0;
}

メモ化再帰で解いてみる

再帰

  • これはTLE
  • 計算量は$O(mn)$
#include <bits/stdc++.h>
using namespace std;

#define int long long

const int INF = 1e15;

int dp[55555];
int c[22];

int n, m;

int rec(int money) {
  if (money == 0) {
    return 0;
  }

  int ans = INF;
  for (int i = 0; i < m; i++) {
    if (money - c[i] < 0) continue;
    ans = min(ans, rec(money - c[i]) + 1);
  }

  return ans;
}

signed main() {
  cin >> n >> m;
  for (int i = 0; i < m; i++) {
    cin >> c[i];
  }

  cout << rec(n) << endl;

  return 0;
}

メモ化再帰

  • 蟻本のナップサックのメモカ再帰っぽく書ける
  • 計算量はたぶん$O(nm)$
#include <bits/stdc++.h>
using namespace std;

#define int long long

const int INF = 1e15;

int dp[55555];
int c[22];

int n, m;

int rec(int money) {
  // 終了条件
  if (money == 0) {
    return dp[money] = 0;
  }

  // 計算済みならその値を返す
  if (dp[money] != INF) {
    return dp[money];
  }

  int ans = INF;
  for (int i = 0; i < m; i++) {
    if (money - c[i] < 0) continue;
    ans = min(ans, rec(money - c[i]) + 1);
  }

  // 計算した値をメモする
  return dp[money] = ans;
}

signed main() {
  cin >> n >> m;
  for (int i = 0; i < m; i++) {
    cin >> c[i];
  }

  fill(dp, dp + n + 10, INF);
  cout << rec(n) << endl;

  return 0;
}