题目思路:这道题目其实很一道很经典的动态规划题目,题目意思很好理解,就是找从起点到终点的所有可行的路径。
约束的两个条件:
机器人每次只能往右或者往下走
机器人不能越界
我们看到这张图就明白一切:
从起点1开始 当i>1 j>1时, 到达第2行第2列的格子有2种路径, 第2行第3列有3中路径....
方法一:经典使用dp数组
有了上面的两个条件,我们就可以解决这个题目了。
我们定义一个二维dp数组,dp[i] [j] 表示从起点到我当前位置(i行j列)有多少条可行的路径,因为我们从约束条件中可以知道,机器人每次只能往右或者往下走,则我们当前点必定是从上面或者左边走过来的(除边界外)。
当然,如果在地图的最上面或者最左边的话,最上面的点只能是从左边走到的,最左边的点只能是从上面走到的。
则我们可以定义状态方程:
当 i > 1 && j > 1 : dp[i] [j] = dp[i] [j-1] + dp[i-1] [j]
当 i = 0:dp[0] [j] = dp[0] [j-1]
当 j = 0:dp[i] [0] = dp[i-1] [0]
import java.util.*; public class Solution { /** * * @param m int整型 * @param n int整型 * @return int整型 */ public int uniquePaths (int m, int n) { int[][] dp = new int[m][n]; for (int i = 0; i < m; i++) { for (int j = 0; j < n; j++) { // 当 i = 0:dp[0][j] = dp[0][j-1] if (i == 0) { // 都是1是因为dp[0][j] = dp[0][j-1],所以干脆全部赋值为1 dp[i][j] = 1; continue; } // 当 j = 0:dp[i][0] = dp[i-1][0] if (j == 0) { dp[i][j] = 1; continue; } // 当 i > 1 && j > 1 : dp[i][j] = dp[i][j-1] + dp[i-1][j] dp[i][j] = dp[i][j-1] + dp[i-1][j]; } } // 返回到达终点的所有可行路径 return dp[m-1][n-1]; } }