动态规划解决带权值的最小路径和
2022/2/3 23:46:57
本文主要是介绍动态规划解决带权值的最小路径和,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
动态规划解决带权值的最小路径和
问题描述:
状态F(i,j): 从(0,0)到达(i,j)的最短路径和
转移方程: F(i,j):min(F(i,j-1),F(i-1,j))+array[i][j]
第一行:F(0,j):F(0,j-1)+array[0][j]
第一列:F(i,0):F(i-1,0)+array[i][0]
初始状态: F(0,0)=array[0][0]
返回 F(row-1,col-1)
代码:
import java.util.*; public class Solution { /** * * @param grid int整型二维数组 * @return int整型 */ public int minPathSum (int[][] grid) { // write code here int row=grid.length; int col=grid[0].length; //如果为空或者只有一行返回0 if(row==0 || col==0){ return 0; } //F(0,0), F(0,i), F(i,0)初始化 for(int i=1;i<row;i++){ grid[i][0]=grid[i-1][0]+grid[i][0]; } for(int i=1;i<col;i++){ grid[0][i]=grid[0][i-1]+grid[0][i]; } //F(i,j) = min{F(i-1,j) , F(i,j-1)} + (i,j) for(int i=1; i<row;i++){ for(int j=1;j<col;j++) { grid[i][j]=Math.min(grid[i-1][j],grid[i][j-1])+grid[i][j]; } } return grid[row-1][col-1]; } }
运行结果:
这篇关于动态规划解决带权值的最小路径和的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-05-29DataGrip使用ssh连接数据库的操作流程
- 2024-05-28SpringBoot3.2更新声明!
- 2024-05-28中外程序员到底有啥区别?
- 2024-05-25外企也半夜发布上线吗?
- 2024-05-24鸿蒙原生应用再新丁!芒果TV 入局鸿蒙
- 2024-05-22基本概念
- 2024-05-22检索数据
- 2024-05-22排序数据
- 2024-05-22基础过滤数据
- 2024-05-22通过逻辑操作符过滤数据