机器人寻路
·
题目描述：
将机器人放在一个m×n的矩阵的左上角，机器人每次只能向右或者向下走一步，现在机器人向走到右下角，请问有多少种可能的走法？
思路分析：
这是典型的动态规划的问题，指定任意一个格子，它可以向右或者向下移动一格，所以动态方程很明显是：res[i][j] = res[i-1][j] + res[i][j-1]。
另外对于最上面一行，由于只能由机器人往右走到达，所以第一行的每个格子都只有一种方法到达，同样的情况适用于第一列，所以我们现在有两组初始值，再根据这两组初始值从第二行第二列开始依次求出其他位置格子的到达路径个数。
代码如下：
public class RobotsFindPath {
public int getPaths(int m, int n) {
int[][] dp = new int[m][n];
for(int i = 0; i < n; i++) {
dp[0][i] = 1;
}
for(int i = 0; i < m; i++) {
dp[i][0] = 1;
}
for(int i = 1; i < m; i++) {
for(int j = 1; j < n; j++) {
dp[i][j] = dp[i-1][j] + dp[i][j-1];
}
}
return dp[m-1][n-1];
}
}
DAMO开发者矩阵，由阿里巴巴达摩院和中国互联网协会联合发起，致力于探讨最前沿的技术趋势与应用成果，搭建高质量的交流与分享平台，推动技术创新与产业应用链接，围绕“人工智能与新型计算”构建开放共享的开发者生态。
更多推荐
0
0- 0
已为社区贡献2条内容
所有评论(0)