机器人走方格I

[编程题]机器人走方格I

热度指数：13794 时间限制：C/C++ 3秒，其他语言6秒空间限制：C/C++ 32M，其他语言64M
算法知识视频讲解

给定两个正整数int x,int y，代表一个x乘y的网格，现有一个机器人要从网格左上角顶点走到右下角，每次只能走一步且只能向右或向下走，返回机器人有多少种走法。保证x＋y小于等于12。

测试样例：

2,2

返回：2

算法知识视频讲解

查看答案及解析

推荐

莱昂纳多

由于题目中x+y<=12，所以不必担心递归超时问题，对于每一步，只要没有走到
边缘（x==1||y==1）就会有两种选择：向下走（x-1）or 向右走（y-1），终
止条件即走到边缘，只能一直走下去，即此时只有一种走法。

class Robot {
public:
    int countWays(int x, int y) {
        // write code here
        if(x<=0||y<=0) return 0;
        if(x==1||y==1) return 1;
        return countWays(x-1,y)+countWays(x,y-1);
    }
};

编辑于 2015-08-18 19:34:00 回复(21)