一天一只顽猴想去从山脚爬到山顶，途中经过一个有个N个台阶的阶梯，但是这猴子有一个习惯： 每一次只能跳1步或跳3步，试问猴子通过这个阶梯有多少种不同的跳跃方式？
解答要求时间限制：1000ms, 内存限制：100MB 输入输入只有一个整数N（0<N<=50）此阶梯有多少个阶梯
输出输出有多少种跳跃方式（解决方案数）
样例输入样例 1 复制
3 50
输出样例 1
2 122106097提示样例 1
提示 思路：动态规划，数组，递归 代码：
// we have defined the necessary header files here for this problem.
// If additional header files are needed in your program, please import here.
int main()
{
int A[55] = {0};
int N;
A[1] = 1;
A[2] = 1;
A[3] = 2;
for(int i = 4;i<51;i++)
{
A[i] = A[i-1]+A[i-3];
}
while(scanf("%d",&N)!=EOF)
{
printf("%d\n",A[N]);
}
// please define the C input here. For example: int n; scanf("%d",&n);
// please finish the function body here.
// please define the C output here. For example: printf("%d\n",a);
return 0;
}