首页 > 试题广场 >

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

Ron

/*基本动态规划*/
    public int countWays(int x, int y) {
        // write code here
        int[][] dp = new int[x][y];
    	dp[0][0] = 1;
    	for(int i = 1; i < x; i++){
    		dp[i][0] = dp[i-1][0];
    	}
    	for(int i = 1; i < y; i++){
    		dp[0][i] = dp[0][i-1];
    	}
    	for(int i = 1; i < x; i++){
    		for(int j = 1; j < y; j++){
    			dp[i][j] = dp[i-1][j] + dp[i][j-1];
    		}
    	}
    	return dp[x-1][y-1];
    }

发表于 2015-11-06 14:39:10 回复(4)

鈞嘢嘢

// 题目要求走的是大格子而不是网格线的交点，所以有两种走法。
// 二维数组用于计算走到当前格子的走法总数，为其上方格子走法总数与其左侧格子走法总数之和
public int countWays(int x, int y) {
        // write code here
        int[][] dp = new int[13][13];
        for (int i = 1; i < y; i++)
            dp[0][i] = 1;
        
        for (int i = 1; i < x; i++)
            dp[i][0] = 1;
        
        for (int i = 1; i < x; i++)
            for (int j = 1; j < y; j++)
            	dp[i][j] = dp[i-1][j] + dp[i][j-1];
        
        return dp[x-1][y-1];
    }

编辑于 2016-07-09 00:46:43 回复(0)

pcW

class Robot {
public:
    int countWays(int x, int y) {
        // write code here
        return factorial(y,x+y-2)/factorial(1,x-1);
    }
    
    int factorial(int f,int t){
        int res=1;
        for(int i=f;i<=t;i++){
            res = res*i;
        }
        return res;
    }
};

全新角度解决问题。

机器人只能右走，或者下走。那么它经过的道路就自然分为水平和竖直，为了到达y点它经过的水平和竖直道路数是恒定的，水平=x-1, 竖直=y-1，将机器人经过的道路依次排列出来，无非是水平竖直的组合。那么机器人从x点走到y点的所有走法就显而易见了=

当时被问怎么证明正确性，一脸懵逼。每一步数学推理都在那还要我怎么证明正确性。。。。。

发表于 2016-06-21 11:07:18 回复(8)

L0L

 int countWays(int x, int y) {
    	if(x==1||y==1)	return 1;
        return countWays(x-1,y)+countWays(x,y-1); 
    }

发表于 2015-10-01 23:25:25 回复(0)

Java

大闲人柴毛毛

机器人在X*Y的矩阵中走，每一步都有两种选择：要么向下、要么向右。

如果向下走，问题就变成：求(X-1)*Y矩阵中机器人的走法；

如果向右走，问题就变成：求X*(Y-1)矩阵中机器人的走法；

显然是递归的思想！

既然是递归，再考虑退出条件：当整个矩阵只有一行或一列的时候只有一种走法。

public class Robot {
    public int countWays(int x, int y) {
        if ( x==1 || y==1 ) 
            return 1;
        
        return countWays(x-1,y)+countWays(x,y-1);
    }
}

发表于 2017-04-02 15:15:00 回复(2)

0pandas0

class Robot {
public:
    int countWays(int x, int y) {
        // write code ,here
        int dp[13][13]={0};
        dp[0][0]=0;
        for(int i=1;i<y;i++)//第一行初始化，因为只有横着走一种方法。
             dp[0][i]=1;
         for(int i=1;i<x;i++)//第一列初始化，因为只有竖着一种方法。
            dp[i][0]=1;
         for(int i=1;i<x;i++)//dp[i][j]的方法，等于走到上面一格和走到左边一个方法之和。
              for(int j=1;j<y;j++){
                  dp[i][j]=dp[i-1][j]+dp[i][j-1];
              }
         return dp[x-1][y-1];       
    }
};

编辑于 2015-09-18 20:10:17 回复(4)

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)

丷柠檬

//动规

import java.util.*;

public class Robot {

public int countWays(int x, int y) {

// write code here

int[][] array = new int[x+1][y+1];

for(int i=0;i<=x;i++){array[i][0]=0;array[i][1]=1;}

for(int j=0;j<=y;j++){array[0][j]=0;array[1][j]=1;}

for(int i=2;i<=x;i++)

for(int j=2;j<=y;j++){

array[i][j]=array[i][j-1]+array[i-1][j];

}

return array[x][y];

}

发表于 2016-07-01 22:37:14 回复(0)

C++

木析

动态规划，dp[i][j]=dp[i-1][j]+dp[i][j-1]，可在此基础上简化为一维数组：

class Robot {
public:
    int countWays(int x, int y) {
        //dp[i][j]=dp[i-1][j]+dp[i][j-1]
        vector<int> dp(y+1,0);
        dp[0]=1;
        for(int i=0;i<x;++i) {
            for(int j=1;j<y;++j) {
                dp[j]+=dp[j-1];
            }
        }
        return dp[y-1];
    }
};

发表于 2021-09-26 19:32:46 回复(0)

lmz9509

/*
递归解法详解：
countWays(int x, int y)表示当前的格子为x*y
因此我们有两种终止条件和一个递归条件
当x==0||y==0表示该表格不存在，走法为0
当x==1||y==1表示该表格为 x*1 或 1*y，那么走到终点只有一种方法
剩下的情况则由递归条件操作，
当前的走法 = 他的上一格走法 + 他左边格子的走法
*/
public 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);
    }
}

发表于 2020-07-02 10:58:18 回复(0)

C/C++

j-217

动态规划思考：

0	1	1	1	1	1
1
1
1
1					E

设行号为r，列号为c，起点S，终点E

1. 到终点E的走法有两种，从上侧[r-1][c]或从左侧[r][c-1]而来，因此可以写出动态方程：

dp[r][c] = dp[r-1][c] + dp[r][c-1]

2. 动态方程的初始化：

起点S的走法有0种，其余第一行只能从左侧走，因此均为1，同理第一列只能从上侧走，同样为1

3. 结合以上条件将表格填写完整，最终求得E的解

代码如下：

class Robot {
public:
    int countWays(int x, int y) {
        int dp[x][y];
        dp[0][0] = 0;
        for (int i = 1; i < x; ++i) {
            dp[i][0] = 1;
        }
        for (int i = 1; i < y; ++i) {
            dp[0][i] = 1;
        }
        for (int r = 1; r < x; ++r) {
            for (int c = 1; c < y; ++c) {
                dp[r][c] = dp[r-1][c] + dp[r][c-1];
            }
        }
        return dp[x-1][y-1];
    }
};

编辑于 2020-03-20 00:11:08 回复(0)

C/C++

Debug丶

class Robot {
public:
    int countWays(int x, int y) {
        // write code here
        int* pDP = new int[y];
        for (int i = 0; i < y; ++i)
            pDP[i] = 1;
        
        for (int i = 1; i < x; ++i)
            for (int j = 1; j < y; ++j)
                pDP[j] = pDP[j - 1] + pDP[j];
        
        int nRes = pDP[y - 1];
        delete[] pDP;
        return nRes;
    }
};

发表于 2019-08-27 17:31:08 回复(0)

zbbsyx

class Robot {
public:
    int countWays(int x, int y) {
        // write code here
        int dp[x][y];
        for (int i = 0; i < x; ++i)
            for (int j = 0; j < y; ++j) {
                dp[i][j] = 0;
            }
            
        dp[0][1] = 1;dp[1][0] = 1;
        for (int i = 0; i < x; ++i) {
            for (int j = 0; j < y; ++j) {
                if(i - 1 >= 0) dp[i][j] += dp[i-1][j];
                if(j - 1 >= 0) dp[i][j] += dp[i][j-1];
            }
        }
        return dp[x-1][y-1];
    }
};

发表于 2019-06-11 15:50:05 回复(0)

ID84848484

//典型动态

//初始化dp[0][j]=1,dp[i][0]=1

//状态转移方程dp[i][j]=dp[i-1][j]+dp[i][j-1];

import java.util.*;

public class Robot {
    public int countWays(int x, int y) {
        // write code here
        int[][] dp=new int[x][y];
        for(int i=0;i<x;i++){
            dp[i][0]=1;
        }
        for(int i=0;i<y;i++){
            dp[0][i]=1;
        }
        for(int i=1;i<x;i++){
            for(int j=1;j<y;j++){
                dp[i][j]=dp[i-1][j]+dp[i][j-1];
            }
        }
        return dp[x-1][y-1];
    }
}

发表于 2019-05-26 23:35:25 回复(1)

C/C++

但求八月九月好运！

//就很简单哦
class Robot {
public:
    int countWays(int x, int y) {
        if(x==1||y==1) return 1;
        return countWays(x,y-1)+countWays(x-1,y);
    }
};

发表于 2019-05-15 20:28:34 回复(0)

航小天

可以在最初时都初始化为1
class Robot {
public:
    int countWays(int x, int y) {
        // write code here
        vector<vector<int>> dp(x,vector<int>(y,1));
        for(int i = 1; i < x; ++i)
            for(int j = 1; j < y;++j)
                dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
        return dp[x - 1][y - 1];
    }
};

发表于 2019-03-28 15:15:19 回复(0)

木然猫猫

动态规划

class Robot {
public:
    int countWays(int x, int y) {
        int F[20][20]{0};
        for (int i=1; i<x; ++i) {
            F[i][0] = 1;
        }
        for (int i=1; i<y; ++i) {
            F[0][i] = 1;
        }
        for (int i=1; i<x; ++i) {
            for (int j=1; j<y; ++j) {
                F[i][j] = F[i-1][j] + F[i][j-1];
            }
        }
        return F[x-1][y-1];
    }
};

运行时间：3ms

占用内存：460k

编辑于 2018-12-29 13:18:26 回复(0)

王先生666

import java.util.*;

public class Robot {
public int countWays(int x, int y) {
//使用动态规划的思想。
//使用数学知识，其中，（m+n-2，m-1）排列组合
int a = x + y -2;
int b = x - 1;
int m = 1, d = 1 ;
for(int i = a; i > a - b ; i--){
m *= i;
}
for(int j = 1; j <= b; j++){
d *=j;
}
return m / d;
}

}

编辑于 2018-05-28 15:44:29 回复(0)

chenlelele

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

发表于 2018-04-02 19:04:44 回复(0)

甘小爵

考虑原始DP问题为二维数组表示当前位置的步数，显然有: dp[i][j] = dp[i-1][j] + dp[i][j-1]，而容易发现dp数组可以压缩为1维存储空间dp[y]。原dp[i-1][j]为上一行当前列的步数，而现dp[j]就存储了上一次该列的步数，而现dp[j-1]为左节点的步数即原dp[i][j-1]。

所以变为：dp[j] = dp[j] + dp[j-1].

class Robot {
public:
    int countWays(int x, int y) {
        // write code here
        int dp[y];
        for(int i = 0; i < y; i++)
            dp[i] = 1;
        for(int i = 1; i < x; i++){
            for(int j = 1; j< y; j++){
                dp[j] = dp[j] + dp[j-1];
            }
        }
        return dp[y-1];
    }
};

编辑于 2017-08-12 19:09:32 回复(0)