Day33 | Part2
约 239 个字 34 行代码 预计阅读时间 1 分钟
转为求二叉树叶子节点的个数, 利用dfs (如图)
- TLE 38/63 cases passed(N/A)
| int dfs(int i, int j, int m, int n) {
if(i > m || j > n) return 0; // 越界
if(i == m && j == n) return 1; //找到了叶子节点
return dfs(i + 1, j, m, n) + dfs(i, j + 1, m, n);
}
int uniquePaths(int m, int n) {
return dfs(1, 1, m, n);
}
|
利用DP → 机器人从(0,0) 位置出发，到(m - 1,n - 1)终点
dp[i][j]：表示从(0,0)出发，到(i, j)有dp[i][j]条不同的路径dp[i][j] 只能从两个方向来,即dp[i][j] = dp[i - 1][j] + dp[i][j - 1]- 初始化:
dp[i][0] = 1，因为从(0, 0)的位置到(i, 0)的路径只有一条, dp[0][j]也同理
- 从左到右一层一层遍历
- 举例: 如图
| int uniquePaths(int m, int n) {
vector<vector<int>> dp(m, vector<int>(n));
for(int i = 0; i < m; i ++) dp[i][0] = 1;
for(int j = 0; j < n; j ++) dp[0][j] = 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];
}
|
dp[i][j]：表示从(0,0)出发，到(i, j)有dp[i][j]条不同的路径-
dp[i][j] = dp[i - 1][j] + dp[i][j - 1]
(i, j)若是障碍的话应该就保持初始状态（初始状态为0）
-
如果(i, 0)这条边有了障碍，障碍之后的dp[i][0]为初始值0, (0,j)同理
- 从左到右一层一层遍历
- 举例→ 如图
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16 | int uniquePathsWithObstacles(vector<vector<int>>& obstacleGrid) {
int m = obstacleGrid.size(), n = obstacleGrid[0].size();
vector<vector<int>> dp(m, vector<int>(n, 0));
// 若起点或终点有障碍,直接返回
if(obstacleGrid[m - 1][n - 1] == 1 || obstacleGrid[0][0] == 1) return 0;
// dp数组初始化
for(int i = 0; i < m && obstacleGrid[i][0] == 0; i ++) dp[i][0] = 1;
for(int j = 0; j < n && obstacleGrid[0][j] == 0; j ++) dp[0][j] = 1;
// 遍历求dp数组
for(int i = 1; i < m; i ++)
for(int j = 1; j < n; j ++) {
if(obstacleGrid[i][j] == 1) continue; // 又障碍,跳过
dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
}
return dp[m - 1][n - 1];
}
|
