DP :求存在的路径是多少
思路: DP
- 状态表示:f[i][j] 表示走到第i行第j列一共有多少种走法
- 状态计算:集合可以划分为:从左边走到g[i][j], 从上面走到g[i][j]
- 参考: yxc
题目描述
* @ lc app=leetcode id=63 lang=cpp
*
* [63] Unique Paths II
* https://leetcode.com/problems/unique-paths-ii/description/
* algorithms
* Medium (33.62%)
* Likes: 984
* Dislikes: 161
* Total Accepted: 221.1K
* Total Submissions: 657.1K
* Testcase Example: '[[0,0,0],[0,1,0],[0,0,0]]'
*
* A robot is located at the top-left corner of a m x n grid (marked 'Start' in
* the diagram below).
*
* The robot can only move either down or right at any point in time. The robot
* is trying to reach the bottom-right corner of the grid (marked 'Finish' in
* the diagram below).
*
* Now consider if some obstacles are added to the grids. How many unique paths
* would there be?
*
* An obstacle and empty space is marked as 1 and 0 respectively in the grid.
*
* Note: m and n will be at most 100.
*
* Example 1:
*
* Input:
* [
* [0,0,0],
* [0,1,0],
* [0,0,0]
* ]
* Output: 2
*
* Explanation:
* There is one obstacle in the middle of the 3x3 grid above.
* There are two ways to reach the bottom-right corner:
* 1. Right -> Right -> Down -> Down
* 2. Down -> Down -> Right -> Right
c++ 代码
class Solution {
public:
int uniquePathsWithObstacles(vector<vector<int>>& obstacleGrid) {
//状态表示: 走到第i行第j列一共有多少种走法
//状态计算: 考虑i,j点,从左边走过来,从上边走过来
int m = obstacleGrid.size();
int n = obstacleGrid[0].size();
vector<vector<long long>> f(m, vector<long long>(n));
for (int i = 0; i < m; i ++ )
for (int j = 0; j < n; j ++ )
{
// 难点一:记得判断当前格子是否时障碍物(1为障碍物,所以g[i][j]应该等于零)
// 注意:if(i) 表示:i是不为零的数, 因为i == 0,为false
// 所以 if(!i) 表示:i为零
if (obstacleGrid[i][j]) continue;
// 特判
if (!i && !j) f[i][j] = 1;
// 难点二:
// 当前点在第一行时不能从上边走过来
// 当前点在第时不一列能从左边走过来
// 从上面走过来情况(不是第一行)
if (i) f[i][j] += f[i - 1][j];
// 从左面走过来(不是第一列)
if (j) f[i][j] += f[i][j - 1];
}
return f[m - 1][n - 1];
}
};
python 代码
class Solution:
def uniquePathsWithObstacles(self, nums: List[List[int]]) -> int:
n = len(nums)
m = len(nums[0])
if n == 0:
return 0
if nums[0][0] == 1:
return 0
dp = [[0 for j in range(m)] for i in range(n)]
dp[0][0] = 1
for i in range(n):
for j in range(m):
if nums[i][j] == 1:
continue
if i > 0:
dp[i][j] += dp[i-1][j]
if j > 0:
dp[i][j] += dp[i][j-1]
return dp[n-1][m-1]