寒假水83——跳舞毯 【DP】

寒假水83——跳舞毯 【DP】

由于长期缺乏运动，小黑发现自己的身材臃肿了许多，于是他想健身，更准确地说是减肥。 
小黑买来一块圆形的毯子，把它们分成三等分，分别标上A,B,C，称之为“跳舞毯”，他的运动方式是每次都从A开始跳，每次都可以任意跳到其他块，但最后必须跳回A，且不能原地跳.为达到减肥效果，小黑每天都会坚持跳n次，有天他突然想知道当他跳n次时共几种跳法，结果想了好几天没想出来－_－ 
现在就请你帮帮他，算出总共有多少跳法。 

Input测试输入包含若干测试用例。每个测试用例占一行，表示n的值(1<=n<=1000)。 
当n为0时输入结束。 
Output每个测试用例的输出占一行，由于跳法非常多，输出其对10000取模的结果.Sample Input

2
3
4
0

Sample Output

2
2
6

#include<iostream>  
#include<string.h>  
#include<stdio.h>  
#include<math.h>  using namespace std;int dp[1001][3]; int main()  
{  int i,n;dp[1][1]=0;dp[1][2]=1;  dp[1][3]=1;  for(i=2;i<=1000;i++)  {  dp[i][1]=dp[i-1][2]+dp[i-1][3];  dp[i][2]=dp[i-1][1]+dp[i-1][3];  dp[i][3]=dp[i-1][1]+dp[i-1][2];  dp[i][1]=dp[i][1]%10000;  dp[i][2]=dp[i][2]%10000;  dp[i][3]=dp[i][3]%10000;  }    while(scanf("%d",&n),n)  {  printf("%dn",dp[n][1]);  }  return 0;  
} 

题解：DP题。

dp[i][1]表示第i步在A;

dp[i][2]表示第i步在B;

dp[i][3]表示第i步在C；

那么，他在A，他之前必在B或C；同理。

dp[i][1]=dp[i-1][2]+dp[i-1][3];

dp[i][2]=dp[i-1][1]+dp[i-1][3];

dp[i][3]=dp[i-1][1]+dp[i-1][2]。