题解 | #挤奶路径#
挤奶路径
https://www.nowcoder.com/practice/6ab56cedae0646e19fb64b8bdbad82a6
考察的知识点:动态规划;
解答方法分析:
- 定义一个二维数组dp,其中dp[i][j]表示从起点到达位置(i, j)的不同路径数目。
- 初始化dp数组。由于只能向下或向右移动,所以第一行和第一列的位置只能从左方或上方到达,因此,如果某个位置有障碍物或者其左方或上方有障碍物,则该位置的路径数为0,否则为1。
- 使用动态规划的思想来递推整个dp数组。对于位置(i, j),从左方和上方到达,到达位置(i, j)的路径数等于到达其左方位置(i-1, j)的路径数加上到达其上方位置(i, j-1)的路径数,即dp[i][j] = dp[i-1][j] + dp[i][j-1]。但是如果位置(i, j)有障碍物,则路径数为0,即dp[i][j] = 0。
- 返回结果dp[m-1][n-1]。
所用编程语言:C++;
完整编程代码:↓
class Solution { public: int uniquePathsWithObstacles(vector<vector<int> >& cows) { int m = cows.size(); int n = cows[0].size(); vector<vector<int> > dp(m, vector<int>(n)); for (int i = 0; i < m; i++) { if (cows[i][0] == 1) { break; } dp[i][0] = 1; } for (int j = 0; j < n; j++) { if (cows[0][j] == 1) { break; } dp[0][j] = 1; } for (int i = 1; i < m; i++) { for (int j = 1; j < n; j++) { if (cows[i][j] == 1) { dp[i][j] = 0; } else { dp[i][j] = dp[i - 1][j] + dp[i][j - 1]; } } } return dp[m - 1][n - 1]; } };