大家好,我是吴师兄,今天分享一道微软一面面试题。
这道题目作为算法题出现,最早可以追溯到 1994 年的 IOI(国际信息学奥林匹克竞赛)的 The Triangle。
时光飞逝,经过 20 多年的沉淀,往日的国际竞赛题如今已经变成了动态规划的入门必做题,不断督促着我们学习和巩固算法。
来看题目描述:
给定一个三角形 triangle ,找出自顶向下的最小路径和。
每一步只能移动到下一行中相邻的结点上。相邻的结点 在这里指的是 下标 与 上一层结点下标 相同或者等于 上一层结点下标 + 1 的两个结点。
“输入:triangle = [[2],[3,4],[6,5,7],[4,1,8,3]] 输出:11 解释:如下面简图所示 ”
img
自顶向下的最小路径和为 11(即,2 + 3 + 5 + 1 = 11)。
这道题目的解法还挺多的:
本题我们采取方法 3 的思路处理,我录了一个 20 分钟的视频进行讲解,有动画,有手写 Java 代码环节。
参考代码如下:
// 登录 AlgoMooc 官网获取更多算法图解
// https://www.algomooc.com
// 作者:程序员吴师兄
// 三角形最小路径和( LeetCode 120 ):https://leetcode-cn.com/problems/triangle/
class Solution {
public int minimumTotal(List<List<Integer>> triangle) {
// triangle 是个二维数组
// 先获取 triangle 的层数,即一维数组的个数
int n = triangle.size();
// 设置一个一维数组,动态的更新每一层中当前节点对应的最短路径
int[] dp = new int[ n + 1 ];
// 从最后一层开始计算节点的最短路径,直到顶层 0 层为止
for (int i = n - 1 ; i >= 0 ; i-- ){
// dp 中存储的是前 i 个位置存储的是到达第 i 层各个节点的最小路径和
// 从每一层的第 0 个位置开始
for(int j = 0 ; j <= i ; j++){
// dp[j] 表示第 i 层中第 j 个节点的最小路径和
dp[j] = triangle.get(i).get(j) + Math.min(dp[j],dp[j+1]);
}
}
// 返回结果
return dp[0];
}
}
提交结果如下: