题解 | #走方格的方案数#
走方格的方案数
https://www.nowcoder.com/practice/e2a22f0305eb4f2f9846e7d644dba09b
方法一：递归
递归说明：n行m列的走法可以看作有n-1行m列最后向下走+n行m-1列最后向右走的走法数之和，即(n,m)=(n-1,m)+(n,m-1)。当只有一条边缘线时就只有一种走法。
#include <stdio.h>
int stack(int a,int b){
if(a==0 || b==0){
return 1;
}
else{
return stack(a-1,b)+stack(a,b-1);
}
}
int main(){
int n,m;
while(scanf("%d %d",&n,&m)!=EOF){
printf("%d",stack(n,m));
}
}
时间复杂度：O(2^N)，空间复杂度：O(N) N=max(n,m)
方法二：动态规划
递归的逆向思维，从最(0,0)开始填dp数组，直到填满
#include <stdio.h>
int main(){
int n,m,i,j;
while(scanf("%d %d",&n,&m)!=EOF){
int dp[n+1][m+1];
for(i=0;i<=n;i++){//初始化
dp[i][0]=1;
}
for(j=0;j<=m;j++){
dp[0][j]=1;
}
for(i=1;i<=n;i++){
for(j=1;j<=m;j++){
dp[i][j]=dp[i-1][j]+dp[i][j-1];
}
}
printf("%d",dp[n][m]);
}
}
时间复杂度：O(nm)，空间复杂度：O(nm) 
投递拼多多集团-PDD等公司10个岗位 >
这些经历跟硬件都没啥关系呀