USACO 2.3 Money Systems (DP 動态規劃)

#include <stdio.h>
#define DEBUG 1
#define TESTCASES 9

//ways[coinageValueIndex][constructedMoney]表示考慮前coinageValueIndex種錢币湊成constructedMoney的數量的錢時的方案數，第coinageValueIndex種錢币可以選或者不選
//數組很大要聲明為全局變量，如果聲明為局部變量棧會溢出
long long ways[26][10001];

int main(){
#if DEBUG
	int testCase;
	for (testCase = 1; testCase <= TESTCASES; testCase++){
		char inputFileName[20] = "inputX.txt";
		inputFileName[5] = '1' +  (testCase - 1);
		freopen(inputFileName, "r", stdin);
		printf("\n#%d\n", testCase);
#endif

	 int typesOfCoins, moneyToConstruct;
	 scanf("%d%d", &typesOfCoins, &moneyToConstruct);
		
	 int coinageValueArray[26];
	 int coinageValueIndex;
	 for (coinageValueIndex = 1; coinageValueIndex <= typesOfCoins; coinageValueIndex++)
		 scanf("%d", &coinageValueArray[coinageValueIndex]);

	 int constructedMoney;
	 for (coinageValueIndex = 0; coinageValueIndex <= typesOfCoins; coinageValueIndex++)
		 for (constructedMoney = 0; constructedMoney <= moneyToConstruct; constructedMoney++)
			if (constructedMoney == 0)
				ways[coinageValueIndex][constructedMoney] = 1;
			else
				ways[coinageValueIndex][constructedMoney] = 0;
		 
	 for (coinageValueIndex = 1; coinageValueIndex <= typesOfCoins; coinageValueIndex++)
		 for (constructedMoney = 1; constructedMoney <= moneyToConstruct; constructedMoney++)
			if (constructedMoney < coinageValueArray[coinageValueIndex] )
				ways[coinageValueIndex][constructedMoney] = ways[coinageValueIndex - 1][constructedMoney];
			else
				//ways[coinageValueIndex][constructedMoney - coinageValueArray[coinageValueIndex]]可以通過遞增周遊constructedMoney的方式來優化ways空間成關于constructedMoney的一維數組,又因為當constructedMoney < coinageValueArray[coinageValueIndex]時，ways[coinageValueIndex][constructedMoney] = ways[coinageValueIndex - 1][constructedMoney]是以遞增周遊constructedMoney的時候可以直接從constructedMoney = coinageValueArray[coinageValueIndex]開始周遊
				ways[coinageValueIndex][constructedMoney] = ways[coinageValueIndex - 1][constructedMoney] +
														ways[coinageValueIndex][constructedMoney - coinageValueArray[coinageValueIndex]];
	 
	printf("%lld\n", ways[typesOfCoins][moneyToConstruct]);

#if DEBUG
	}
#endif
	return 0;
}