问题

棋盘的左上角有一个过河卒，需要走到右下角。卒行走的规则：可以向下、或者向右。

现在要求你计算出卒从左上角能够到达右下角的路径的条数。

思路

一、卒子可以随便向右向下走，那么可以想到，一个卒子只能从 当前格子的左侧格子 和 当前格子的上方格子上走到当前格子。
那么假设从 $(1,1)$ 走到 当前格子的左侧格子 的路径条数是 $x$，从 $(1,1)$ 走到 当前格子的上方格子 的路径条数是 $y$，那么从 $(1,1)$ 走到当前格子的路径条数就应该是 $x+y$ 。

其实我们已经得到了一个动态规划的转移方程，设 $f(i,j)$ 表示从 $(1,1)$ 格子走到当前格子的路径条数，那么根据上一段得到的结论，可以得到： $f(i,j) = f(i-1,j) + f(i,j-1)$ 。

二、假设棋盘的长和宽为 $n$ ，从左上角到右下角的路径长度恒为 $2n$ ，向右和向左的长度均为 $n$ 。
即从 $2n$ 个中任选 $n$ 个，根据排列组合的知识，总的路径条数为 $C_{2n}^{n}$ 。

代码

#include <iostream>

using namespace std;

const int N = 110;

int f[N][N];

int main()
{
    int n, m;
    scanf("%d%d", &n, &m);
    f[1][1] = 1;

    for (int i = 1;i <= n;i ++ )
        for (int j = 1;j <= n;j ++ )
            if(i != 1 || j != 1) f[i][j] = f[i - 1][j] + f[i][j - 1];

    for (int i = 1;i <= n;i ++ ) printf("%d ",f[i][i]);
    return 0;
}

测试

考虑 $ n = m$ 的情况，即棋盘的长与宽是相同的。

输入：6 6
输出：1 2 6 20 70 252

问题

长和宽长度相等的棋盘，只能走右上角的一半或左下角的一半，计算出从左上角能够到达右下角的路径的条数。

思路

棋盘只能走一半，路径条数为卡特兰数：1, 1, 2, 5, 14, 42, 132, 429......
通项公式：$f(n) = \dfrac{C_{2n}^{n}}{n + 1}$