【題解】ZeroJudge d253: 00674 – Coin Change

#include <iostream>
#include <cstring>
using namespace std;
int coins[] = {1, 5, 10, 25, 50};
int dp[5][7500];

int ways(int idx, int money){
    if (idx == 5 || money < 0) return 0;
    if (money == 0) return 1;
    if (dp[idx][money] != -1) return dp[idx][money];
    int ret = 0;
    for (int i = idx; i < 5; i++){
        if (money >= coins[i]){
            ret += ways(i, money - coins[i]);
        }
    }
    return dp[idx][money] = ret;
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int n;
    memset(dp, -1, sizeof(dp));
    while (cin >> n){
        cout << ways(0, n) << "\n";
    }
    return 0;
}

#include <iostream>
#include <cstring>
using namespace std;

const int maxn = 7500;
int N = 5; // types of coins
int coin[] = {1, 5, 10, 25, 50};
long long dp[maxn];

int main() {
    int n;
    memset(dp, 0, sizeof(dp));
    dp[0] = 1;
    for (int i=0; i<N; i++) {
        for (int j=coin[i]; j<maxn; j++) {
            dp[j] = dp[j] + dp[j-coin[i]];
        }
    }
    
    while (cin >> n) {
        cout << dp[n] << "\n";
    }
    return 0;
}

N = [1, 5, 10, 25, 50]

lenN = len(N)
maxn = 7489+5
dp = [0] * maxn
dp[0] = 1
for i in range(lenN):
    for j in range(N[i], maxn):
        dp[j] += dp[j - N[i]]

while True:
    try:
        M = int(input())
        print(dp[M])
    except:
        break