猫和老鼠玩象棋，玩了M+N局，猫赢了M局 老鼠赢了N局 N>M，而且在整个过程中，猫的得分从来没有超过过老鼠，问共有多少种可能的比赛得分过程
先用学习数学的时候常常使用的方法，简化，推测的方法，
试推一下(N,M)的得分过程 与 （N-1, M） (N, M-1)的关系
假设猫和老鼠一共玩了X盘象棋，则X = M + N
X取值
(N, M)
组合种类(N的数据用1表示，M的数据用0表示)
1
(1, 0)
1
2
(2, 0) (1, 1)
11 10
3
(3, 0) (2, 1)
111 110 101
4
(4,0)(3,1)
(2,2)
11111110 1101 10111100 1010
TO组合
From组合
how得到（末尾）
(2,0)
(1,0)------1
+1
(1,1)
(1,0)------1
+0
(3,0)
(2,0)------11
+1
(2,1)
(1,1)------10(2,0)------11
+1+0
(4,0)
(3,0)------111
+1
(3,1)
(2,1)------110 101(3,0)------111
+1+0
(2,2)
(2,1)----- 110 101
+1
设用fun(N,M)表示,上面的数据可以推论出
fun(N,M) = fun(N-1, M) + fun(N, M-1) 当 N > M
fun(N, M-1) 当 N = M
0 当 N < M
现在证明该等式的正确性。
当 N < M 时，与题目不符合，没有合适的得分过程， fun = 0.
当 N = M时，根据猫的得分从没有超过老鼠可以得出最后一次比赛中为猫赢。即组合的结尾都是0，即前面的N+M-1次比赛中，老鼠赢N次，猫赢了M-1次，即fun(N, M-1)的组合。所以等式成立
当 N > M 时，若末尾为鼠赢，则前面N+M-1次为猫赢M次，鼠赢N-1次，即fun(N-1, M)
若末尾为猫赢，则前面N+M-1次为猫赢M-1次，鼠赢N次，即fun(N, M-1) ，等式成立。
算法可用可用动态规划来实现：
#include "stdafx.h"
#include <iostream>
#include <string>
#include <cassert>
using namespace std;
const int N = 3;
const int M = 2;
int number[N + 1][M + 1] = {0};
void calculate(int nIndex, int mIndex)
{
if (nIndex < mIndex)
{
return;
}
if ((nIndex > 1) && (nIndex > mIndex))
{
number[nIndex][mIndex] += number[nIndex - 1][mIndex];
}
if (mIndex > 0)
{
number[nIndex][mIndex] += number[nIndex][mIndex - 1];
}
}
int main(void)
{
int nIndex = 0;
int mIndex = 0;
assert(N >= M);
number[1][0] = 1;
for (nIndex = 1; nIndex <= N; nIndex++)
{
for (mIndex = 0; (mIndex <= nIndex) && (mIndex <= M); mIndex++)
{
calculate(nIndex, mIndex);
}
}
cout << "N =" << N << ";/nM = " << M << ";/nnumber = " << number[N][M] << endl;
}
