UniquePaths，UniquePaths2，路径问题。动态规划。
2024-08-22 17:25:06
UniquePaths：给定m*n矩阵，从（0，0）到（m-1，n-1）路径条数。只能向下向右走。
算法分析：这和爬楼梯问题很像，到（m，n）的路径数是到（m-1，n)和（m，n-1）路径和。第一行，第一列，为边界条件。
public class UniquePaths
{
//动态规划，非递归
public int uniquePaths(int m, int n)
{
int[][] a = new int[m][n];
for(int i = 0; i < m; i ++)//初始条件，第一行第一列
{
a[i][0] = 1;
}
for(int i = 0; i < n; i ++)
{
a[0][i] = 1;
}
for(int i = 1; i < m; i ++)
{
for(int j = 1; j < n; j ++)
{
a[i][j] = a[i-1][j]+a[i][j-1];//递推公式
}
}
return a[m-1][n-1];
} //动态规划递归
public int uniquePaths2(int m, int n)
{
if(m == 1 || n == 1) return 1;
else
{
return uniquePaths2(m-1, n)+uniquePaths2(m, n-1);
}
}
}
UniquePaths2：在上一题基础上，矩阵为1的点是障碍。求路径数。
public class UniquePaths2
{
public int uniquePathsWithObstacles(int[][] obstacleGrid)
{
int m = obstacleGrid.length;
int n = obstacleGrid[0].length;
if(obstacleGrid[0][0] == 1 || obstacleGrid[m-1][n-1] == 1)//特例
{
return 0;
}
for(int i = 0; i < m; i ++)//边界条件，第一行第一列，如果碰到1，则后面所有都为0
{
if(obstacleGrid[i][0] == 1)
{
for(int j = i; j < m; j ++)
{
obstacleGrid[j][0] = 0;
}
break;
}
else
{
obstacleGrid[i][0] = 1;
}
}
for(int i = 1; i < n; i ++)
{
if(obstacleGrid[0][i] == 1)
{
for(int j = i; j < n; j ++)
{
obstacleGrid[0][j] = 0;
}
break;
}
else
{
obstacleGrid[0][i] = 1;
}
} for(int i = 1; i < m; i ++)
{
for(int j = 1; j < n; j ++)
{
if(obstacleGrid[i][j] == 1)
{
obstacleGrid[i][j] = 0;
}
else
{
obstacleGrid[i][j] = obstacleGrid[i-1][j] + obstacleGrid[i][j-1];
}
}
}
return obstacleGrid[m-1][n-1];
}
}
最新文章
- 3. Builder（建造者）
- Nginx图片剪裁模块探究 http_image_filter_module
- RedHat7 部署ELK日志分析系统
- Eclipse中user library包管理
- e3.tree参考手册
- 网站相关人员信息记录humans.txt
- Python函数篇（二）之递归函数、匿名函数及高阶函数
- oracle中nvarchar2查询结果显示总是少一位
- 【汤鸿鑫 3D太极】5年目标规划（基本功、套路、实战搏击）
- nginx介绍 - 部署到linux中
- centos6下安装opencv3
- CSS 的 ID 和 Class 有什么区别，如何正确使用它们。
- DM6467开发领航-开发坏境安装
- Unreal Engine 4 笔记
- es索引的RestHighLevelClient实现
- 是否升级IOS11？IOS11不支持32位程序 查看手机哪些APP不支持
- Mysql中datetime和timestamp区别
- 使用XWAF框架（3）——下载文件
- 版本控制工具（下）——Git的远程仓库、分支管理与其它操作
- RxSwift 系列(五)