Minimum Path Sum，最短路径问题，动态规划
2024-09-22 11:59:46
问题描述：Given a m x n grid filled with non-negative numbers, find a path from top left to bottom right which minimizes the sum of all numbers along its path.
问题分析：参考路径问题，其实就是加权的路径问题，求最小的权值和。动态规划问题，核心递推公式，d[i][j] = min(d[i-1][j],d[i][j-1])+a[i][j].
public class MinPathSum
{
public int minPathSum(int[][] grid)
{
for(int i = 1; i < grid.length; i ++)//初始化第一行第一列
{
grid[i][0] += grid[i-1][0];
}
for(int i = 1; i < grid[0].length; i ++)
{
grid[0][i] += grid[0][i-1];
}
for(int i = 1; i < grid.length; i ++)
{
for(int j = 1; j < grid[0].length; j ++)
{
grid[i][j] = Math.min(grid[i-1][j], grid[i][j-1])+grid[i][j];//核心递推公式
}
}
return grid[grid.length-1][grid[0].length];
}
}
最新文章
- LCS
- UISegmentControl
- Boo who
- picurl
- JavaScript 题目破解过程与解析
- c#中DropDownList控件绑定枚举数据
- IntelliJ IDEA 15 创建maven项目
- C# IL DASM 使用
- sql 不同server間寫入數據
- linux下 链接 sqlserver数据库 驱动的安装
- Primavera 6.0
- Spring Security-用户密码自定义加密
- Mycat 配置
- 顺便说说webservice
- Markdown 语法手册 （完整整理版）
- tornado自定义session
- Vue源码解析---数据的双向绑定
- Luogu4423 BJWC2011 最小三角形 平面最近点对
- vbox 的 ova 提取vmdk 与 vdi 以及扩容
- MySQL 中的反引号(`)：是为了区分 MySql 关键字与普通字符而引入的符号；一般，表名与字段名都使用反引号。