关于苹果的一道面试题
今天早上在微薄上看到的苹果公司的一道面试题
自己做了一个下，不知道对不对，高手们分享一下思路呗
题目：
一个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
[其他解释]
恩啊，但是答案是多少呢
[其他解释]
为什么要2^6呢，依据是什么？
[其他解释]
答案是30
解法。类菲波拉契分析，得到的其实是一个等差数列，差值为2,初值为0
结果其实就是，等差数列求和公式。Sn=na1+n(n-1)d/2; 初值为0，差值为2,简化为n*(n-1)
n=2 sn=2*1=2
n=3 sn=3*2=6
n=4 sn=4*3=12
n=5 sn=5*4=20
n=6 sn=6*5=30
[其他解释]
不对 》。。。
[其他解释]
924 没用程序 用数学知识算出来的
[其他解释]
怎么算的？关键是过程，你这答案貌似不对。。。。
[其他解释]
X=1,Y=1
最终变为X=6;Y=6
X,Y只能递增
那就是说X++;Y++的排列
X需要加5次，Y需要加5次，总共10次。
把X++看作是0，Y++看作为1
看一次排列：0000011111
由此想到10个位置，往里面填5个1，剩下的5个为0
那不就是10个位置里面挑5个吗？
C 10 5 = 252