Project Euler Problem 31

リンク

解法(C++)

#include <iostream>
using namespace std;

#define MAX_WIDTH 999
#define MAX_HEIGHT 9

int coins[] = {1,2,5,10,20,50,100,200};
int table[MAX_WIDTH][MAX_HEIGHT];

long solve(int sum, int n);

int main(void){
    for(int i=0;i<MAX_WIDTH;i++){
        table[i][1] = 1; //1で払う方法は常に1通り
    }
    cout << solve(200, 8) << endl;
}

long solve(int sum, int n){
    /* メモ化再帰 */
    if(table[sum][n]) return table[sum][n];//計算済みの値があれば利用する
    table[sum][n] = 0;
    for(int t=0;sum - t*coins[n-1] >= 0;t++){
        table[sum][n] += solve(sum - t*coins[n-1], n-1);
    }
    return table[sum][n];
}

戻る