动态规划之Triangle(三角形) Java实现
程序员文章站
2022-07-03 19:38:12
问题给定一个三角形的数字阵列,选择一条自顶向下的路径,使得沿途的所有数字之和最小。(每一步只能移动到相邻的格子中)如上图所示的三角形阵列,其最小路径之和为11(2+3+5+1)。...
问题
给定一个三角形的数字阵列,选择一条自顶向下的路径,使得沿途的所有数字之和最小。(每一步只能移动到相邻的格子中)
如上图所示的三角形阵列,其最小路径之和为11(2+3+5+1)。
问题分析
我们对该三角形阵列从最底层求起,用一个result数组存放每一层的数的较小值和其相邻的上面一层的数之和,直到遍历到顶层,返回result[0]。
以本题为例:
1、我们先新建一个result数组,其里面的值都是0,0的较小值还是0,然后遍历其相邻的上面一层的数并求之和,得到result数组中的值为[0+4,0+1,0+8,0+3],即[4,1,8,3]。
2、同理,遍历[4,1,8,3]的较小值和遍历[4,1,8,3]的相邻的上一层的数[6,5,7]之和,得到result数组中的值为[1+6,1+5,3+7],即[7,6,10]。
3、同理,遍历[7,6,10]的较小值和遍历[7,6,10]的相邻的上一层的数[3,4]之和,得到result数组中的值为[6+3,6+4],即[9,10]。
4、同理,遍历[9,10]的较小值和遍历[9,10]的相邻的上一层的数[2]之和,得到result数组中的值为[9+2],即[11]。
5、返回result[0],即11。
java代码实现
import java.util.ArrayList;
import java.util.List;
/**
* @author mazhen
* @className Triangle
* @Description TODO
* @date 2020/12/29 16:07
*/
public class Triangle {
public static void main(String[] args) {
List<Integer> inList1 = new ArrayList<>();
inList1.add(2);
List<Integer> inList2 = new ArrayList<>();
inList2.add(3);
inList2.add(4);
List<Integer> inList3 = new ArrayList<>();
inList3.add(6);
inList3.add(5);
inList3.add(7);
List<Integer> inList4 = new ArrayList<>();
inList4.add(4);
inList4.add(1);
inList4.add(8);
inList4.add(3);
List<List<Integer>> outList = new ArrayList<>();
outList.add(inList1);
outList.add(inList2);
outList.add(inList3);
outList.add(inList4);
System.out.println(minTriangle(outList));
}
public static int minTriangle(List<List<Integer>> list) {
if (null == list)
return 0;
int outListSize = list.size();
if (outListSize == 0)
return 0;
if (outListSize == 1)
return list.get(0).get(0);
//用于存放相加后的结果
int[] result = new int[list.size()+1];
//外层list从后往前遍历
for (int j=outListSize-1;j>=0;j--) {
//获取内层list
List<Integer> inList = list.get(j);
int inSize = inList.size();
for (int i=0;i<inSize;i++) {
//取result中的最小值与内部list中的值相加后写入到result数组中
result[i] = Math.min(result[i],result[i+1]) + inList.get(i);
}
}
return result[0];
}
}
本文地址:https://blog.csdn.net/mameng1988/article/details/111651778