题目描述
给定一个n*m的方格阵,沿着方格的边线走,从左上角(0,0)开始,每次只能往右或者往下走一个单位距离,问走到右下角(n,m)一共有多少种不同的走法。
样例
输入
2 3
输出
10
算法1
(动态规划) $O(mn)$
空间复杂度$O(mn)$
这道题的数据规模也太小了。。。
1<=m,n<=10;
a[i][j]表示走到坐标为(i,j)的坐标点上的方法数
由于只能向右或向下走
每个坐标点都可以从它左边或者上边的点走到
所以可以推出
a[i][j]=a[i-1][j]+a[i][j-1];
第一列上所有的点都只能从(0,0)向下直走抵达,所以方法数都为1
第一行同理
C 代码
#include<stdio.h>
int a[11][11];
int main()
{
int m,n,i,j;
scanf("%d%d",&m,&n);
a[0][0]=1;
for(i=1;i<=m;i++) a[i][0]=1;
for(i=1;i<=n;i++) a[0][i]=1;
for(i=1;i<=m;i++)
for(j=1;j<=n;j++)
a[i][j]=a[i-1][j]+a[i][j-1];
printf("%d",a[m][n]);
return 0;
}
算法2
(空间优化) $O(mn)$
空间复杂度$O(n)$
由于抵达每个点方法数都是本行的左边和正上方的点相加得的
所以内层循环依然顺序遍历就好
如果是用到了上一行左边的点(比如杨辉三角)
需要把内层循环改为倒序遍历
C 代码
#include<stdio.h>
int a[11];
int main()
{
int m,n,i,j;
scanf("%d%d",&m,&n);
for(i=0;i<=n;i++) a[i]=1;
for(i=1;i<=m;i++)
for(j=1;j<=n;j++)
a[j]+=a[j-1];
printf("%d",a[n]);
return 0;
}
%%%%%%%%%
%%%%
大佬第一个居然也是题解%%%
大佬太强了orz
%%%%