URAL 1225 Flags(DP 동적 계획)

#include <stdio.h>
#define MAX_STRIPES 45
#define COLORS 3
#define RED 0
#define WHITE 1
#define BLUE 3
 
int numOfStripes;
/* 
 *     0 (numOfStripes- 1)         
 *    tail   (                  )     color ，waysOfTailColor[tail][color]   0 tail            
 *                  ，     waysOfTailColor[tail][RED] waysOfTailColor[tail][WHITE]    
 */
long long waysOfTailColor[MAX_STRIPES][COLORS - 1];//       2^45 -3^45  ,  long long


int main(){

	scanf("%d", &numOfStripes);
	waysOfTailColor[0][RED] = waysOfTailColor[0][WHITE] = 1;
	waysOfTailColor[1][RED] = waysOfTailColor[1][WHITE] = 1;
	
	int tail;
	for (tail = 1; tail < numOfStripes; tail++){
		/* 
		 *            ，               ，    
		 *   waysOfTailColor[tail][RED] = waysOfTailColor[tail - 1][WHITE] + waysOfTailColor[tail - 1][BULE];
		 *                ，            
		 *   waysOfTailColor[tail - 1][BULE] = waysOfTailColor[tail - 2][WHITE]
		 *   waysOfTailColor[tail][RED] = waysOfTailColor[tail - 1][WHITE] + waysOfTailColor[tail - 2][WHITE]
		 * waysOfTailColor[tail][WHITE] waysOfTailColor[tail][RED]  
		 */
		waysOfTailColor[tail][RED] = waysOfTailColor[tail - 1][WHITE] + waysOfTailColor[tail - 2][WHITE];
		waysOfTailColor[tail][WHITE] = waysOfTailColor[tail - 1][RED] + waysOfTailColor[tail - 2][RED];
	}

	int waysOfColor = waysOfTailColor[numOfStripes - 1][RED] + waysOfTailColor[numOfStripes - 1][WHITE];
	//  long long     
	printf("%I64d
", waysOfColor);

	return 0;
}