NYOJ 1076 计划数（公式要么递归）

方案数量

时间限制：1000 ms | 内存限制：65535 KB

难度：2

描写叙述

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

输入

多组測试数据。

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

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

输出

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

例子输入

4 3
2 2
0 0

例子输出

35
6

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

一、推公式

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

#include <cstdio>

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
", 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 <cstdio>
#include <cstring>

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
", dp[n][m]);
    }
    return 0;
}

NYOJ 1076 计划数（公式 要么 递归）

方案数量

NYOJ 1076 计划数（公式要么递归）