题解 | #走方格的方案数#

#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;
}