关于苹果的一道面试题
今天早上在微薄上看到的苹果公司的一道面试题
自己做了一个下，不知道对不对，高手们分享一下思路呗
题目：
一个6X6宫格图，你从左上角出发，目的地是右下角。中途只可以往右或者向下移动，能有多少路线到达终点？
我的答案：
计算的思路是 左上角的方块有两种路线，最右侧一列和最底侧一行只有一种路线，最右下角有0种路线。
2X2 的情况： 2种路线的方块有1个 1种路线的方块有两个 0种路线的方块有1个 组合成一条完整的线路需要再除以2
所以 2X2 的情况下的路径数是：（2X1+1X1+0X1）/2=2种
3X3 的情况 是（2X4+1X4+0X1）/2=6种
依次类推，
6X6的情况下 是（25X2+10X1 +0X1）/2=30种
不知道对不对，求答案。
另，想用程序来实现，求思路。
[最优解释]
哦，我上面错了，算到4的时候，搞错忘了算2边过来的东西了
其实他还是类似菲波拉契分析的那种分析，因为只能向右和向下，那么就意味这东西只能从左和上面来
那么把左边的情况和上面的情况分别统计一下就好了，也就是每一个点都需要依靠前面的左边和上面的点来即时，过程和菲波拉契数列很像
[其他解释]
汗！想错了！！！
public static int sum = 0;
const int n = 6;
static void Main(string[] args)
{
fun(0, 0);
Console.WriteLine(sum);
Console.ReadLine();
}
public static void fun(int x, int y)
{
if (x == n-1 && y ==n-1)
{
sum++;
return;
}
if (x < n)
{
fun(x + 1, y);
}
if (y < n)
{
fun(x, y + 1);
}
}
[其他解释]
如果求条数，这个其实是菲波拉契数列变体
如果求具体一条路径，这个则是“贪婪+回溯”
如果求所有路径，这个是“遍历有向图/树”
[其他解释]
不懂算法好多年了。
[其他解释]
我觉得6X6的情况下 是2^6-1=250
[其他解释]
