算法训练营Day39(动态规划)
- 开发
- 56
-
62.不同路径
62. 不同路径 - 力扣(LeetCode)
class Solution {
public int uniquePaths(int m, int n) {
//1dp数组 m n代表位置,dp[m][n]代表到达这里的途径个数
int [][] dp = new int[m][n];
//3初始化
for(int i = 0;i<n;i++){
dp[0][i] = 1;
}
for(int j = 0;j<m;j++){
dp[j][0] = 1;
}
//4遍历顺序
for(int i = 1;i<m;i++){
for(int j = 1;j<n;j++){
//2递推公式
dp[i][j] = dp[i-1][j]+dp[i][j-1];
}
}
return dp[m-1][n-1];
}
}
63. 不同路径 II
63. 不同路径 II - 力扣(LeetCode)
class Solution {
public int uniquePathsWithObstacles(int[][] obstacleGrid) {
int m = obstacleGrid.length;
int n = obstacleGrid[0].length;
int [][] dp = new int [m][n];
//如果在起点或终点出现了障碍,直接返回0
if (obstacleGrid[m - 1][n - 1] == 1 || obstacleGrid[0][0] == 1) {
return 0;
}
for(int i = 0;i<n;i++){
if(obstacleGrid[0][i]==1){
break;
}
dp[0][i]=1;
}
for(int j=0;j<m;j++){
if(obstacleGrid[j][0]==1) break;
dp[j][0] = 1;
}
for(int i = 1;i<m;i++){
for(int j = 1;j<n;j++){
if(obstacleGrid[i][j]==0){
dp[i][j] = dp[i-1][j] +dp[i][j-1];
}
}
}
return dp[m-1][n-1];
}
}
原文地址:https://blog.csdn.net/weixin_65728526/article/details/135422154
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。
本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。
如若转载,请注明出处:https://www.suanlizi.com/kf/1745079045223223296.html
如若内容造成侵权/违法违规/事实不符,请联系《酸梨子》网邮箱:1419361763@qq.com进行投诉反馈,一经查实,立即删除!