算法学习——动态规划之点数值三角形的最小路径
2023-02-18 16:39:51 时间
算法描述
在一个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]);
}
结果
相关文章
- Ubuntu 16.04 LTS 安装redis
- redis系列之初识Redis
- Redis系列之如何高效使用
- NLP: Text Neural Network (Part1: textRNN, textCNN)
- [NetWork] 局域网基本原理
- Redis实现朋友圈,微博等Feed流功能,实现Feed流微服务(代码实现)
- 下载速率提升40% ,《斗罗大陆:魂师对决》是如何做到的?
- 华为Awareness kit,您旅途路上的超智能管家
- Discovery直播 | 移动应用“通行证”——钥匙环,解锁管家式安全出行服务
- 教你在“狼人杀”中实现变声效果
- 技术与艺术的结合,HMS Core让手机主题趣味丛生
- 受众同步管理功能上线,让你的活动礼包发对人
- 分析服务助力产品运营
- 租房买房行业报告上线,为房产服务数字化转型添砖加瓦
- 放码来战!HMS Core线上Codelabs挑战赛正式开始
- 一图读懂DCI版权服务
- 【HMS Core 6.0全球上线】Toolkit,您的智能辅助编程好帮手
- 眼镜选款新方法,用AR+Scene技术实现3D虚拟试戴
- HDD成都站:HMS Core 6.0带来新可能,多元服务驱动产品价值提升
- Insights直播预告 | 多媒体管线服务,助您轻松进入“技术流”创新阵地