NYOJ 1076 方案數量（公式 或 遞推）

NYOJ 1076 方案數量（公式 或 遞推）

方案數量

描述

給出一個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 

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