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

//递归做法
// #include<stdio.h>
// int fun(int m,int n)
// {
//     if(m==0||n==0)
//         return 1;
//     else
//         return fun(m,n-1)+fun(m-1,n);
//     }
// int main()
// {
//     int m,n;
//     while(scanf("%d%d",&n,&m)!=EOF)
//     {
//         printf("%d\n",fun(m,n));
//     }
// }


//排列组合的方法
// #include<stdio.h>
// int main()
// {
//     int n, m;

//     while(scanf("%d %d", &n, &m) != EOF) 
//     {
//         int up = 1, down = 1;
//         for(int i=0; i<n; i++) 
//         {
//             up *= m+n-i;
//             down *= i+1;
//         }
//         printf("%d\n", up/down);
//     }
// }


//动态规划做法
#include<stdio.h>
int main()
{
    int n, m;

    while(scanf("%d %d", &n, &m) != EOF) {
        int i, j, dp[n+1][m+1];

        for(i=0; i<=n; i++) {
            for(j=0; j<=m; j++) {
                if(i == 0 && j == 0) {
                    dp[i][j] = 1;
                    continue;
                }

                if(i == 0)
                    dp[i][j] = dp[i][j-1];
                else if(j == 0)
                    dp[i][j] = dp[i-1][j];
                else
                    dp[i][j] = dp[i][j-1] + dp[i-1][j];
            }
        }
        printf("%d\n", dp[n][m]);
    }
}