题解 | #走方格的方案数#
走方格的方案数
https://www.nowcoder.com/practice/e2a22f0305eb4f2f9846e7d644dba09b
#include <stdio.h>
int main() {
int a, b;
while (scanf("%d %d", &a, &b) != EOF) {
int dp[a+1][b+1];
dp[0][0]=1;
for(int i=0;i<=a;i++)
{
for(int j=0;j<=b;j++)
{
if((i!=0&&j==0)||(i==0&&j!=0))
{
dp[i][0]=1;
dp[0][j]=1;
continue;
}
dp[i][j]=dp[i-1][j]+dp[i][j-1];
}
}
printf("%d\n", dp[a][b]);
}
return 0;
}
使用动态规划解题，设dp[i][j]为到达坐标（i,j）处的走法。通过任意选一点坐标稍微研究下，可以得到
dp[i][j]=dp[i-1][j-1]+dp[i][j-1](i!=0或j!=0);
若i=0或者j=0的坐标，由于题目规定只能向下或者向右，且不能返回，所以这些点的走法就只能有一种，即
dp[0][j]=1;
dp[i][j]=1;
这道题就顺利解决了
查看30道真题和解析