MGJ9. 方格走法
描述
有一个X*Y的网格,小团要在此网格上从左上角到右下角,只能走格点且只能向右或向下走。请设计一个算法,计算小团有多少种走法。给定两个正整数int x,int y,请返回小团的走法数目。输入描述
输入包括一行,空格隔开的两个正整数x和y,取值范围[1,10]。输出描述
输出一行,表示走法的数目示例1
输入:
3 2
输出:
10
C 解法, 执行用时: 1ms, 内存消耗: 368KB, 提交时间: 2020-05-20
#include<stdio.h> long long a[] = {0,1,2,6,24,120,720,5040,40320,362880,3628800,39916800,479001600,6227020800,87178291200,1307674368000,20922789888000,355687428096000,6402373705728000,121645100408832000,2432902008176640000}; int main() { int x,y; scanf("%d %d", &x, &y); printf("%lld", a[x+y]/(a[x]*a[y])); return 0; }
C 解法, 执行用时: 2ms, 内存消耗: 344KB, 提交时间: 2021-09-11
#include <stdio.h> int uniquePaths(int m, int n) { if(m<1 || n<1) return 0; if(m==1 || n==1) return 1; return uniquePaths(m,n-1)+uniquePaths(n,m-1); } int main() { int x,y; scanf("%d %d",&x,&y); printf("%d\n",uniquePaths(x+1,y+1)); return 0; }
C 解法, 执行用时: 2ms, 内存消耗: 352KB, 提交时间: 2019-07-03
#include<stdio.h> long long a[] = {0,1,2,6,24,120,720,5040,40320,362880,3628800,39916800,479001600,6227020800,87178291200,1307674368000,20922789888000,355687428096000,6402373705728000,121645100408832000,2432902008176640000}; int main() { int x,y; scanf("%d %d", &x, &y); printf("%lld", a[x+y]/(a[x]*a[y])); return 0; }
C 解法, 执行用时: 2ms, 内存消耗: 360KB, 提交时间: 2020-05-16
#include<stdio.h> long long a[] = {0,1,2,6,24,120,720,5040,40320,362880,3628800,39916800,479001600,6227020800,87178291200,1307674368000,20922789888000,355687428096000,6402373705728000,121645100408832000,2432902008176640000}; int main() { int x,y; scanf("%d %d", &x, &y); printf("%lld", a[x+y]/(a[x]*a[y])); return 0; }
C++14 解法, 执行用时: 2ms, 内存消耗: 360KB, 提交时间: 2020-03-12
#include<cstdio> int main(){ int x,y; scanf("%d %d",&x,&y); x+=1,y+=1; int dp[x][y]; for(int i=0;i<x;i++) dp[i][0]=1; for(int i=0;i<y;i++) dp[0][i]=1; for(int i=1;i<x;i++){ for(int j=1;j<y;j++){ dp[i][j]=dp[i-1][j]+dp[i][j-1]; } } printf("%d",dp[x-1][y-1]); }