読者です 読者をやめる 読者になる 読者になる

Project Euler 31

Problem 31

動的計画法の基本的な問題。

using System;

class PE031 {
    static void Main() {
        int[] coins = { 1, 2, 5, 10, 20, 50, 100, 200 };

        const int N = 200;
        int[] dp = new int[N+1];
        dp[0] = 1;
        for (int i = 0; i < coins.Length; i++) {
            for (int j = coins[i]; j <= N; j++) {
                dp[j] += dp[j - coins[i]];
            }
        }
        Console.WriteLine(dp[N]);
    }
}