题解 | #走方格的方案数#
走方格的方案数
https://www.nowcoder.com/practice/e2a22f0305eb4f2f9846e7d644dba09b
#include <stdio.h> #include <string.h> int Cal_dp(int** dp, int index_x, int index_y, int n, int m) { if (index_x==0 || index_y==0) { int cur = (int)*((int*)dp+n*index_y+index_x); // printf("x=0|y=0: dp[%d][%d]=%d\n",index_y, index_x, cur); return cur; } else { int cur, cur1, cur2; cur1 = Cal_dp(dp, index_x-1, index_y, n, m); // printf("dp[%d][%d]=%d\n",index_y, index_x-1, cur1); cur2 = Cal_dp(dp, index_x, index_y-1, n, m); // printf("dp[%d][%d]=%d\n",index_y-1, index_x, cur2); cur = cur1 + cur2; // printf("dp[%d][%d]=%d\n",index_y, index_x, cur); return cur; } } int main() { int n, m; scanf("%d %d\n",&n,&m); int dp[m+1][n+1], i, j; //坐标会到达m和n值本身,再加上因为本质上是考虑的线边缘、即网格点,因此本质上会导致数组尺寸+1 memset(dp, 0, sizeof(dp)); for (i=0; i<=n; i++) { dp[0][i] = 1; } for (j=0; j<=m; j++) { dp[j][0] = 1; // printf("dp[j=%d][0]=%d\n", j, dp[j][0]); } int ans=Cal_dp((int**)dp, n, m, n+1, m+1); printf("%d\n", ans); return 0; }