| F.棋盘 | |||||
| |||||
| Description | |||||
| 现有一棋盘，左上角为起点坐标为(1,1),右下角为终点坐标为(n,n)，现在我们规定棋盘的对角线(1,1),(2,2)....(n,n)上除了起点和终点之外都不能通过，求出从起点到终点的路径数有多少个？ | |||||
| Input | |||||
| 多组测试数据处理到文件结束，每行包含一个整数n(2<=n<=35)。 | |||||
| Output | |||||
| 输出路径数. | |||||
| Sample Input | |||||
| 2
6
| |||||
| Sample Output | |||||
| 2
28
| |||||
| Hint | |||||
| 只能向右或向下走 |
dp可以完成：
#include<iostream>
#include<string.h>
#include<stdio.h>
#include<queue>
#include<stack>
#include<map>
#include<vector>
#include<cmath>
using namespace std;
long long int a[38][38];
int main()
{
//memset(a,-1,sizeof(a));
for(int i=1;i<=36;i++)
{
for(int j=1;j<=36;j++)
{
if(i==j)
a[i][j]=0;
else if(i==1||j==1)
{
a[i][j]=1;
}
else
{
a[i][j]=a[i-1][j]+a[i][j-1];
}
}
}
int n;
while(cin>>n)
cout<<a[n-1][n]+a[n][n-1]<<endl;
return 0;
}
原文：http://www.cnblogs.com/zhanzhao/p/3532966.html