算法学习——动态规划之点数值三角形的最小路径
2023-02-18 16:36:59 时间
算法描述
在一个n行的点数值三角形中,寻找从顶点开始每一步可沿着左斜或者右斜向下直到到达底端,使得每个点上的数值之和为最小
右图为一个4行的点数值三角形
算法思路
-
接收用户输入行数n
-
使用一个二维数组
a[n+1][n+1]
来存放各个点上的数值,数值可以由用户输入或者是随机生成 -
定义一个二维数组(用来存放方向)
direction[n+1][n+1]
,存放1或0,1代表右
,0代表左
-
定义一个二维数组
b[n+1][n+1]
表示到底端的数值之和以上图4行的点数值三角形为例
b[4][1]=47
b[4][2]=93
b[3][1]=43
这里b[3][1]是可以等于47,也可以等于93,但题目要求的是最小,所以这里取小的值
b[3][1]其实是由逆推得到的,具体看下面
-
b[n+1][n+1]的递推关系
-
初始值
从最后一行开始
b[n][i]=a[n][i]
i遍历完最后一行的所有元素 -
递推关系
b[n][i]=Math.min(b[n+1][i],b[n+1][i+1]) 取最小值
-
算法实现
System.out.println("输入数字三角形的行数n:");
Scanner scanner = new Scanner(System.in);
int n = scanner.nextInt();
scanner.close();
int[][] a= new int[n+1][n+1];
//随机赋值数字三角形
for(int i=1;i<n+1;i++){
for(int j =1;j<=i;j++){
a[i][j] = (int) (Math.random()*100);
}
}
//输出数字三角形
for(int i=1;i<n+1;i++){
for(int j =1;j<=i;j++){
System.out.print(a[i][j]+" ");
}
System.out.println("");
}
int[][] b = new int[n+1][n+1];
int[][] direction = new int[n+1][n+1];//0是左,1是右
//最后一行的长度为其本身
for(int i=1;i<n+1;i++){
b[n][i] = a[n][i];
}
//关键逆推代码
for(int i=n-1;i>=1;i--){
for(int j=1;j<=i;j++){
if(b[i+1][j+1]<b[i+1][j]){
b[i][j]=a[i][j] + b[i+1][j+1];
direction[i][j]=1;//右边的数值较小,则记录方向为右
}else{
b[i][j]=a[i][j] + b[i+1][j];
direction[i][j]=0;//左边的数值较小,则记录方向为左
}
}
}
System.out.println("最小路径和为"+b[1][1]);
int flag = 1;
int j=1;
//循坏结束
while(flag!=n){
System.out.print(a[flag][j]);
if(direction[flag][j]==1){
System.out.print("->向右");
flag++;
j++;
}else{
System.out.print("->向左");
flag++;
}
}
System.out.print("->"+a[flag][j]);
}
结果
相关文章
- asp.net mvc 之旅—— 第二站 窥探Controller下的各种Result
- asp.net mvc 之旅—— 第一站 从简单的razor入手
- Sql Server之旅——终点站 nolock引发的三级事件的一些思考
- Sql Server之旅——第十四站 深入的探讨锁机制
- Sql Server之旅——第十三站 对锁的初步认识
- Sql Server之旅——第十二站 sqltext的参数化处理
- Sql Server之旅——第十一站 简单说说sqlserver的执行计划
- Sql Server之旅——第十站 看看DML操作对索引的影响
- Sql Server之旅——第九站 看公司这些DBA们设计的这些复合索引
- Sql Server之旅——第八站 复合索引和include索引到底有多大区别?
- Sql Server之旅——第七站 为什么都说状态少的字段不能建索引
- Sql Server之旅——第六站 使用winHex利器加深理解数据页
- Sql Server之旅——第五站 确实不得不说的DBCC命令(文后附年会福利)
- Sql Server之旅——第四站 你必须知道的非聚集索引扫描
- Sql Server之旅——第三站 解惑那些背了多年聚集索引的人
- Sql Server之旅——第二站 理解万恶的表扫描
- Sql Server之旅——第一站 那些给我们带来福利的系统视图
- 看看C# 6.0中那些语法糖都干了些什么(终结篇)
- 看看C# 6.0中那些语法糖都干了些什么(中篇)
- 看看C# 6.0中那些语法糖都干了些什么(上篇)