二维图的动态规划
因为不能穿越对角线，则选取对角线的一边dp即可
选取对角线右下侧
则x轴上每个点只能由其左侧的点走过去（只有1条）
对角线上的点只能由对角线下方的点走过去
其他点可以由左侧和下侧两种方式到达
因为对角线左上和右下均可
所以答案*2
1 /* 2 Written By. StelaYuri 3 */ 4 #include<stdio.h> 5 long long s[36][36]; 6 int main(){ 7 int n,i,j,N=0; 8 for(i=1;i<=35;i++){ 9 s[i][0]=1; 10 for(j=1;j<i;j++) 11 s[i][j]=s[i][j-1]+s[i-1][j]; 12 s[i][i]=s[i][i-1]; 13 } 14 while(scanf("%d",&n)!=EOF&&n!=-1){ 15 N++; 16 printf("%d %d %lld\n",N,n,s[n][n]*2); 17 } 18 return 0; 19 }
原文：https://www.cnblogs.com/stelayuri/p/12213406.html