机器人走方格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)

Python

你回家了我在等你呢

# -*- coding:utf-8 -*-
class Robot:
def countWays(self, x, y):
# write code here
tmparray=[[0]*(y+1) for _ in range(x+1)]
for i in range(1,x+1):
for j in range(1,y+1):
tmparray[i][j]=tmparray[i-1][j]+tmparray[i][j-1]
if i==1 and j==1:
tmparray[i][j]=1
return tmparray[x][y]

发表于 2019-05-29 12:06:31 回复(0)

Python

华科平凡

python dp solution:

# -*- coding:utf-8 -*-
class Robot:
    def countWays(self, x, y):
        if x == 1 or y == 1: return 1
        dp = [[1 for i in range(y)] for j in range(x)]
        for i in range(1, x):
            for j in range(1, y):
                dp[i][j] = dp[i - 1][j] + dp[i][j - 1]
        return dp[-1][-1]

发表于 2017-10-31 16:27:51 回复(0)

Python

Yannyezixin

# -*- coding:utf-8 -*-
class Robot:
    def countWays(self, x, y):
        # write code here
        x -= 1
        y -= 1
    	f = lambda x: x and x * f(x - 1) or 1
        return f(x + y)/(f(x)*f(y))

发表于 2016-08-04 17:55:14 回复(0)