时间限制：

1000 ms  |  内存限制：

65535 KB

难度：

2

描写叙述

给出一个N*M的棋盘。左下角坐标是（0。0）。右上角坐标是（N，M），规定每次仅仅能向上或者向右走。问从左下角走到右上角，一共同拥有多少种方案。上图是一个4*3的棋盘。

输入

多组測试数据。

每组输入两个整数N，M（0≤N，M≤30）。

输入0,0时表示结束。不做不论什么处理。

输出

对于每组測试数据，输出相应的方案数。

例子输入

4 32 20 0

例子输出

356

分析：这道题有2种做法。

一、推公式

ans = C(n+m, n)。由于从左下角走到右上角一共要走n+m步。往上要走n步，假设用1表示向上走。用0表示向右走。则相当于给n+m个数进行赋值，当中n个数被赋值为1，求有多少种赋值方法。仅仅需从n+m个数里挑出n个，有C(n+m, n)中挑选办法。

#include 
         
          long long get_ans(long long a, long long x) {    long long ans = 1;    for(long long i = 1; i <= a; i++)        ans = ans * (x - i + 1) / i;    return ans;}int main() {    long long n, m;    while(~scanf("%lld%lld", &n, &m) && (n + m)) {        printf("%lld\n", get_ans(n, n + m));    }    return 0;}
         

二、递推

由于假设要到(n, m)点，要么从(n-1, m)点过来，要么从(n, m-1)点过来。设dp[i][j]表示从(0, 0)到(i, j)有多少种方案，

则dp[i][j] = dp[i-1][j] + dp[i][j-1]，最后输出dp[n][m]就是答案。

#include 
         
          #include 
          
           const int N = 32;long long dp[N][N];void get_ans() {    memset(dp, 0, sizeof(dp));    for(int i = 0; i < 31; i++)        dp[i][0] = dp[0][i] = 1;    for(int i = 1; i < 31; i++)        for(int j = 1; j < 31; j++)            dp[i][j] = dp[i-1][j] + dp[i][j-1];}int main() {    get_ans();    int n, m;    while(~scanf("%d%d", &n, &m) && (n + m)) {        printf("%lld\n", dp[n][m]);    }    return 0;}
          
         

版权声明：本文博主原创文章，博客，未经同意不得转载。