【题目链接】：
【题目大意】：
Problem Description
数一很喜欢跑步~喜欢追逐风的脚步~
但是数一永远改不了贪玩调皮的个性，他在跑步的时候经常跑到别的跑道上。假设数一在跑一条直线跑道，从左往右是1号跑道，2号跑道，3号跑道……如此类推，并且为了让数一同学更自由，总共有无限条跑道！数一需要跑n步才能到达终点，但是正如上面所说的，他每跑一步要么仍然在原跑道，要么蹿到相邻的跑道，当然数一是不会跑到1号跑道之外的，因为这是违背数一原则的！数一，顾名思义，肯定是从1号跑道开始跑步，同样的，最后必须回到1号跑道到达终点。那么请问数一有多少种方案来跑完这n步呢？（两种方案视为不同当且仅当两种方案的某一步所在的跑道不同）
Input
多组数据，每组数据一个整数n（n≤1000）
Output
对于每组数据，输出一个整数，表示满足题意的方案数。
Sample Input
235
Sample Output
2421
Hint
n=2时，数一可以有1-2-1或者1-1-1两种方案
n=3时，数一可以有1-2-1-1或者1-1-2-1或者1-2-2-1或者1-1-1-1四种方案
【思路】很容易想到每步方案是有前三个状态推过来，即左边跑道，当前跑道，右边跑道，，写成dp就是：
dp[i][j] = dp[i – 1][j + 1].add(dp[i – 1][j].add(dp[i – 1][j – 1]));DP[i][j]:表示跑到j跑道跑了i步的方案数。
代码：
/** this code is made by herongwei* Problem: 1667* Verdict: Accepted* Submission Date: 2015-09-22 19:51:08* Time: 992MS* Memory: 240620KB*///package ac0901; import java.util.*;import java.io.*;import java.math.*; public class Main{public static void main(String args[]){Scanner cin = new Scanner(new BufferedInputStream(System.in));//int t = cin.nextInt();BigInteger dp[][] = new BigInteger[1101][1101];for(int i=0; i<1100; ++i){for(int j=0; j<1100; ++j){dp[i][j]=BigInteger.ZERO;}}dp[0][0]=BigInteger.ONE;int n;for(int i=1; i<=1001; ++i){for(int j=1; j<=1001; ++j){dp[i][j] = dp[i – 1][j + 1].add(dp[i – 1][j].add(dp[i – 1][j – 1]));}}while(cin.hasNext()){n=cin.nextInt();System.out.println(dp[n+1][1]);}}}
版权声明：本文为博主原创文章，未经博主允许不得转载。
哪怕前方的路会充满坎坷，但为梦想而拼搏的人会永不言败
