原题链接:62. Unique Paths
题干
有一个 m * n 的矩阵,有一个小机器人在左上角,它只能往下或往右走,问到达右下角一共有多少不同的路径?
思路
首先可以确定,一共要走 m + n 步。
要用动态规划的话,需要思考当前的状态,以及与上一个状态有什么关联?然后有了一个关系等式,问题就迎刃而解。
假设某一个状态,小机器人在 (i, j) 位置,此时走了 i + j 步。他的上一个位置可能在 (i - 1, j) 或者 (i, j - 1) 。那此时可能的不同路径数就是 (i - 1, j) 和 (i, j - 1) 处路径数之和。那关系就出来了:
dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])
|
怎么走需要思考一下,因为除了原点,每个点都有很多不确定的路径。所以只能按照广度优先。
代码:
public int uniquePaths(int m, int n) { if (m == 0 || n == 0) { return 0; } if (m == 1 || n == 1) { return 1; } int[][] dp = new int[m][n]; dp[0][0] = 1; for (int step = 1; step <= m + n; step++) { int i = 0; int j = step - i; while (i < m && j >= 0) { if (j < n) { if (i == 0) { dp[i][j] = dp[i][j - 1]; } else if (j == 0) { dp[i][j] = dp[i - 1][j]; } else { dp[i][j] = dp[i - 1][j] + dp[i][j - 1]; } } i++; j = step - i; } } return dp[m - 1][n - 1]; }
|