Combinatorial - Coin Changing Problemの解答(ただし2次元配列)

DPL_1_A_v2.cpp

#include <iostream>
#include <algorithm>

using namespace std;

int main(){
  int n, m;
  int c[21];
  int dp[21][50001];
  cin >> n >> m;
  for (int i = 1; i <= m; i++)
    cin >> c[i];
  for (int i = 0; i <= n; i++) {
    dp[1][i] = i;
  }
  for (int i = 2; i <= m; i++) {
    for (int j = 0; j <= n; j++) {
      if (j >= c[i]) {
        dp[i][j] = min(dp[i][j-c[i]]+1, dp[i-1][j]);
      }
      else {
        dp[i][j] = dp[i-1][j];
      }
    }
  }
  cout << dp[m][n] << endl;
  return 0;
}

コイン問題 | 動的計画法 | Aizu Online Judge http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=DPL_1_A&lang=jp