矩阵走法问题

腾讯2013笔试题：

首先我们研究从A到B有多少种走法，定义f(x，y)，其中x为A到B横向走的格数，y为A到B纵向走的格数，则A到B有f(x，y)中走法，不难看出

1. f(x,y)=f(x-1,y)+f(x,y-1)  

因此f(x,y)问题可以用递归算法来做，其中

1. 递归公式为：f(x,y)=f(x-1,y)+f(x,y-1)  
2. 边界条件为：f(x,0)=f(0,y)=1  

而问题求的是不经过点p的路径数，A到B的路径数为f(7,5),A到P的路径数为f(3,3),P到B的路径数为f(4,2),因此解为f(7,5)-f(3,3)*f(4,2)

1.程序实现代码：

#include <iostream>
using namespace std;

int f(int x,int y)
{
    if(x==0||y==0)
        return 1;
    else
        return f(x,y-1)+f(x-1,y);
}
int main()
{
   cout<<f(7,5)-f(3,3)*f(4,2)<<endl;
}

运行结果：

1. 492  
2.