Algorithm-路径问题-路径个数和路径和
2021/12/18 23:50:01
本文主要是介绍Algorithm-路径问题-路径个数和路径和，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！
62. 不同路径
class Solution {
public int uniquePaths(int m, int n) {
int[][] dp = new int[m][n];
dp[0][0] = 1;
for (int i = 1; i < m; i++) {
dp[i][0] = 1;
}
for (int i = 1; i < n; i++) {
dp[0][i] = 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];
}
}
63. 不同路径 II
class Solution {
public int uniquePathsWithObstacles(int[][] obstacleGrid) {
int m = obstacleGrid.length;
int n = obstacleGrid[0].length;
int[][] dp = new int[m][n];
if (obstacleGrid[0][0] == 1)
return 0;
dp[0][0] = 1;
for (int i = 1; i < m; i++) {
dp[i][0] = (obstacleGrid[i][0] == 1) ? 0 : dp[i - 1][0];
}
for (int i = 1; i < n; i++) {
dp[0][i] = (obstacleGrid[0][i] == 1) ? 0 : dp[0][i - 1];
}
for (int i = 1; i < m; i++) {
for (int j = 1; j < n; j++) {
dp[i][j] = (obstacleGrid[i][j] == 1) ? 0 : dp[i - 1][j] + dp[i][j - 1];
}
}
return dp[m - 1][n - 1];
}
}
64. 最小路径和
class Solution {
public int minPathSum(int[][] grid) {
int m = grid.length;
int n = grid[0].length;
int[][] dp = new int[m][n];
dp[0][0] = grid[0][0];
for (int i = 1; i < m; i++) {
dp[i][0] = dp[i - 1][0] + grid[i][0];
}
for (int i = 1; i < n; i++) {
dp[0][i] = dp[0][i - 1] + grid[0][i];
}
for (int i = 1; i < m; i++) {
for (int j = 1; j < n; j++) {
dp[i][j] = Math.min(dp[i - 1][j], dp[i][j - 1]) + grid[i][j];
}
}
return dp[m - 1][n - 1];
}
}
120. 三角形最小路径和
import java.util.List;
class Solution {
public int minimumTotal(List<List<Integer>> triangle) {
int n = triangle.size();
int[][] dp = new int[n][n];
int ans = Integer.MAX_VALUE;
dp[0][0] = triangle.get(0).get(0);
for (int i = 1; i < n; i++) {
for (int j = 0; j <= i; j++) {
if (j == 0) {
dp[i][j] = dp[i - 1][j] + triangle.get(i).get(j);
} else if (j == i) {
dp[i][j] = dp[i - 1][j - 1] + triangle.get(i).get(j);
} else {
dp[i][j] = Math.min(dp[i - 1][j - 1], dp[i - 1][j]) + triangle.get(i).get(j);
}
}
}
for (int i = 0; i < n; i++) {
ans = Math.min(ans, dp[n - 1][i]);
}
return ans;
}
}
576. 出界的路径数
931. 下降路径最小和
class Solution {
public int minFallingPathSum(int[][] matrix) {
int ans = Integer.MAX_VALUE;
int n = matrix.length;
for (int i = 0; i < n; i++) {
ans = Math.min(ans, find(matrix, i));
}
return ans;
}
private int find(int[][] matrix, int u) {
int n = matrix.length;
int[][] dp = new int[n][n];
for (int i = 0; i < n; i++) {
dp[0][i] = (i == u) ? matrix[0][i] : Integer.MAX_VALUE;
}
for (int i = 1; i < n; i++) {
for (int j = 0; j < n; j++) {
dp[i][j] = Integer.MAX_VALUE;
if (j == 0 && Math.min(dp[i - 1][j], dp[i - 1][j + 1]) != Integer.MAX_VALUE) {
dp[i][j] = Math.min(dp[i - 1][j], dp[i - 1][j + 1]) + matrix[i][j];
} else if (j == n - 1 && Math.min(dp[i - 1][j - 1], dp[i - 1][j]) != Integer.MAX_VALUE) {
dp[i][j] = Math.min(dp[i - 1][j - 1], dp[i - 1][j]) + matrix[i][j];
} else {
if (j > 0 && j < n - 1 && Math.min(dp[i - 1][j - 1], Math.min(dp[i - 1][j], dp[i - 1][j + 1])) != Integer.MAX_VALUE)
dp[i][j] = Math.min(dp[i - 1][j - 1], Math.min(dp[i - 1][j], dp[i - 1][j + 1])) + matrix[i][j];
}
}
}
int ans = Integer.MAX_VALUE;
for (int i = 0; i < n; i++) {
ans = Math.min(ans, dp[n - 1][i]);
}
return ans;
}
}
class Solution {
public int minFallingPathSum(int[][] matrix) {
int n = matrix.length;
int[][] dp = new int[n][n];
for (int i = 0; i < n; i++) {
dp[0][i] = matrix[0][i];
}
for (int i = 1; i < n; i++) {
for (int j = 0; j < n; j++) {
if (j == 0) {
dp[i][j] = Math.min(dp[i - 1][j], dp[i - 1][j + 1]) + matrix[i][j];
} else if (j == n - 1) {
dp[i][j] = Math.min(dp[i - 1][j - 1], dp[i - 1][j]) + matrix[i][j];
} else {
dp[i][j] = Math.min(dp[i - 1][j - 1], Math.min(dp[i - 1][j], dp[i - 1][j + 1])) + matrix[i][j];
}
}
}
int ans = Integer.MAX_VALUE;
for (int i = 0; i < n; i++) {
ans = Math.min(ans, dp[n - 1][i]);
}
return ans;
}
}
1289. 下降路径最小和 II
class Solution {
public int minFallingPathSum(int[][] grid) {
int n = grid.length;
int ans = Integer.MAX_VALUE;
int[][] dp = new int[n][n];
for (int i = 0; i < n; i++) {
dp[0][i] = grid[0][i];
}
for (int i = 1; i < n; i++) {
for (int j = 0; j < n; j++) {
dp[i][j] = Integer.MAX_VALUE;
}
}
for (int i = 1; i < n; i++) {
for (int j = 0; j < n; j++) {
for (int k = 0; k < n; k++) {
if (k == j)
continue;
dp[i][j] = Math.min(dp[i][j], dp[i - 1][k] + grid[i][j]);
}
}
}
for (int i = 0; i < n; i++) {
ans = Math.min(ans, dp[n - 1][i]);
}
return ans;
}
}
1575. 统计所有可行路径
方法1
https://mp.weixin.qq.com/s?__biz=MzU4NDE3MTEyMA==&mid=2247485297&idx=1&sn=5ee4ce31c42d368af0653f60aa263c82&chksm=fd9cac6ecaeb25787e6da90423c5467e1679da0a8aaf1a3445475199a8f148d8629e851fea57&scene=178&cur_album_id=1773144264147812354#rd
import java.util.Arrays;
class Solution {
int[][] cache;
public int countRoutes(int[] locations, int start, int finish, int fuel) {
cache = new int[locations.length][fuel + 1];
for (int i = 0; i < locations.length; i++) {
Arrays.fill(cache[i], -1);
}
return dfs(locations, start, finish, fuel);
}
private int dfs(int[] locations, int curCityId, int finish, int surplusFuel) {
if (cache[curCityId][surplusFuel] != -1)
return cache[curCityId][surplusFuel];
if (surplusFuel == 0 && curCityId != finish) {
cache[curCityId][surplusFuel] = 0;
return cache[curCityId][surplusFuel];
}
boolean hasNext = false;
for (int i = 0; i < locations.length; i++) {
if (i == curCityId)
continue;
int need = Math.abs(locations[i] - locations[curCityId]);
if (surplusFuel >= need) {
hasNext = true;
break;
}
}
if (surplusFuel != 0 && hasNext == false) {
cache[curCityId][surplusFuel] = (curCityId == finish) ? 1 : 0;
}
int sum = (curCityId == finish) ? 1 : 0;
for (int i = 0; i < locations.length; i++) {
if (i == curCityId)
continue;
int need = Math.abs(locations[i] - locations[curCityId]);
if (surplusFuel >= need) {
sum += dfs(locations, i, finish, surplusFuel - need);
sum %= 1000000007;
}
}
cache[curCityId][surplusFuel] = sum;
return sum;
}
}
方法2
https://mp.weixin.qq.com/s?__biz=MzU4NDE3MTEyMA==&mid=2247485319&idx=1&sn=95a3dc9c97ca57185de792ca70924afe&chksm=fd9cac98caeb258ebea466f59378670a90af1cb3015ae70922e1d04ac711a5b8d8d853ac5e7d&scene=178&cur_album_id=1773144264147812354#rd
class Solution {
public int countRoutes(int[] locations, int start, int finish, int fuel) {
int cityNum = locations.length;
int[][] dp = new int[cityNum][fuel + 1];
for (int i = 0; i < fuel + 1; i++) {
dp[finish][i] = 1;
}
for (int cur = 0; cur <= fuel; cur++) {
for (int i = 0; i < cityNum; i++) {
for (int k = 0; k < cityNum; k++) {
if (k == i)
continue;
int need = Math.abs(locations[i] - locations[k]);
if (cur >= need) {
dp[i][cur] += dp[k][cur - need];
dp[i][cur] %= 1000000007;
}
}
}
}
return dp[start][fuel];
}
}
这篇关于Algorithm-路径问题-路径个数和路径和的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！
- 2024-12-24MongoDB资料：新手入门完全指南
- 2024-12-20go-zero 框架的 RPC 服务 启动start和停止 底层是怎么实现的？-icode9专业技术文章分享
- 2024-12-19Go-Zero 框架的 RPC 服务启动和停止的基本机制和过程是怎么实现的？-icode9专业技术文章分享
- 2024-12-18怎么在golang中使用gRPC测试mock数据？-icode9专业技术文章分享
- 2024-12-15掌握PageRank算法核心！你离Google优化高手只差一步！
- 2024-12-15GORM 中的标签 gorm:"index"是什么？-icode9专业技术文章分享
- 2024-12-11怎么在 Go 语言中获取 Open vSwitch (OVS) 的桥接信息（Bridge）？-icode9专业技术文章分享
- 2024-12-11怎么用Go 语言的库来与 Open vSwitch 进行交互？-icode9专业技术文章分享
- 2024-12-11怎么在 go-zero 项目中发送阿里云短信？-icode9专业技术文章分享
- 2024-12-11怎么使用阿里云 Go SDK (alibaba-cloud-sdk-go) 发送短信？-icode9专业技术文章分享
