コイン問題 | 動的計画法 | Aizu Online Judge

DPコースなるものを発見したので解いていこうと思う。

貪欲法でいける？と思ったが、コインの額面が半端なのでDPで解いていく。

int main() {
    int n, m; cin >> n >> m;
    int coins[25];
    int dp[25][50005];
    for (int i = 0; i < m; i++) cin >> coins[i];

    for (int i = 0; i < 25; i++) fill(dp[i], dp[i] + 50005, 1000*1000);
    dp[0][0] = 0;
    for (int i = 0; i < m; i++) {
        for (int j = 0; j <= n; j++) {
            dp[i + 1][j] = min(dp[i + 1][j], dp[i][j]);
            int k = j - coins[i];
            if (k >= 0) {
                dp[i + 1][j] = min(dp[i + 1][j], dp[i][k] + 1);
                dp[i + 1][j] = min(dp[i + 1][j], dp[i + 1][k] + 1);
            }
        }
    }
    printf("%d\n", dp[m][n]);
    return 0;
}