Hust oj 1123 Grid(组合数||dp）

给出下图的一个n*m的一个grid，从左下角出发到达目的地右上角,每次只能沿着图中的线来走，而且每次只能向上或者向右行走，如下图所示两种不同的走法

你能求出从起始点到达目的地的所有不同种类的路径数目吗？

有多组测试数据

每组测试数据包含两个整数n, m(0<=n,m<=5)

根据输入的m,n输出不同的走法数目.

万祥

这道题有两种方法，一种是dp，还有一种是组合数学，因为只能往上走和往右走，所以从左下角走到右上角，必定会经过N个向上的边和M个向右的边，所以总路线 = C(M+N，N)||C(M+N,M)。如果是动态规划法的话，当前位置只能从左边或者下边转移过来，所以很容易就可以得带状态转移方程F[I][j] = F[I-1][j] + F[I][j-1],当然了，边界要特殊处理一下。

#include <cstdio>
using namespace std;int main()
{int m,n;while(scanf("%d%d",&m,&n)!=EOF&&n!=0||m!=0){int a=1,b=1;for(int i=m+n;i>n;i--)a*=i;for(int i=1;i<=m;i++)b*=i;printf("%d\n",a/b);}}