关于苹果的一道面试题
今天早上在微薄上看到的苹果公司的一道面试题 

自己做了一个下，不知道对不对，高手们分享一下思路呗


题目：

一个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
------其他解决方案--------------------

引用:

如果求条数，这个其实是菲波拉契数列变体

如果求具体一条路径，这个则是“贪婪+回溯”

如果求所有路径，这个是“遍历有向图/树”

恩啊，但是答案是多少呢
------其他解决方案--------------------

引用: