大家好，我是苍何。
从开水团大象推送的头条消息了解到，美团刚刚宣布提前一个月发放年终奖，趁着热乎，给大家赶紧做个分享。
具体消息如下：
1、宣布 2025 年人才盘点提前
2、1 月开始人才盘点，3 月开始沟通
3、3 月上旬发年度奖金(去年为四月上旬)
4、4月1号加薪和股票生效
相比于去年，可以说整整提前了一个月，这次提前进行人才盘点，开水团官方给出的解释是，为了提高人才盘点效率，缩短盘点时间。
你也许会很纳闷，年终奖提前发放这种破事居然都能成喜大普奔的大新闻了，笑死。
讲真，年终奖很多互联网公司都有不成文的规定，都喜欢放在年后发放，在三四月份的比较多，所以很多人即使离职也要等到拿了年终再走，刚好金三银四，手握年终奖找工作，找他个一两个月也不慌。
所以，你看啊，哪怕是提前一个月，这也比延后一个月好呀，要是能赶着过年发，那真叫一个完美，拿着年终奖过个年，年夜饭上的肉丸子我都要多吃两个。
不过，开水团这次提前发放的年终奖，据了解，销售和客服的发放时间不变。
开水团今年也曾宣布新的福利政策：
1、推出 5 折员工单车骑行卡，开水团员工骑小单车直接五折。
2、员工每个月只需要花费 1 块钱就可领取价值 100 元的「神会员」省钱包。
感觉开水团这名号可以改改了，办公室不再只有冷冰冰的开水，至少还有内部会员，值了值了，罢了罢了。
好啦，你怎么看年终奖年后发放这事？欢迎评论区讨论。
...
回归主题。
今天来一道美团开发考过的一道面试算法题，给枯燥的牛马生活加加油😂。
题目描述
平台：LeetCode
题号：120
题目名称：三角形最小路径和
给定一个三角形 triangle，找到自顶向下的最小路径和。
每一步只能移动到下一行中相邻的结点。相邻的结点在这里指的是下标与上一层结点下标相同或相差为1的结点。
示例 1：
输入：
triangle = [[2],[3,4],[6,5,7],[4,1,8,3]]
输出：
11
解释：
如下图所示：
2
3 4
6 5 7
4 1 8 3
自顶向下的最小路径和为 11（即 2 → 3 → 5 → 1 = 11）。
示例 2：
输入：
triangle = [[-10]]
输出：
-10
提示：
1≤triangle.length≤2001 \leq \text{triangle.length} \leq 200
triangle[0].length=1\text{triangle[0].length} = 1
triangle[i].length=triangle[i-1].length+1\text{triangle[i].length} = \text{triangle[i-1].length} + 1
−104≤triangle[i][j]≤104-10^4 \leq \text{triangle[i][j]} \leq 10
解题思路
思路解析
该问题是经典的动态规划问题，目标是找到从三角形顶端到达底部的最小路径和。
我们可以使用自底向上的动态规划方法：
定义状态：
设dp[i][j]表示从位置(i, j)到底部的最小路径和。状态转移方程：
自底向上递推，当前位置(i, j)的最小路径和为：dp[i][j]=triangle[i][j]+min(dp[i+1][j],dp[i+1][j+1])dp[i][j] = \text{triangle}[i][j] + \min(dp[i+1][j], dp[i+1][j+1]) 其中，dp[i+1][j]和dp[i+1][j+1]分别表示下一行当前列和下一列的最小路径和。初始化：
最底层的路径和就是triangle的最底层元素，即dp的最后一行与triangle相同。结果：
自顶向下的最小路径和即为dp[0][0]。
代码实现
Java代码
import java.util.List;
public class TriangleMinimumPath {
public int minimumTotal(List<List<Integer>> triangle) {
int n = triangle.size();
int[] dp = new int[n]; // 使用一维数组来优化空间复杂度
// 初始化 dp 数组为三角形最后一行的值
for (int i = 0; i < n; i++) {
dp[i] = triangle.get(n - 1).get(i);
}
// 从倒数第二行开始向上计算
for (int i = n - 2; i >= 0; i--) {
for (int j = 0; j <= i; j++) {
dp[j] = triangle.get(i).get(j) + Math.min(dp[j], dp[j + 1]);
}
}
// 返回顶部的最小路径和
return dp[0];
}
}
C++代码
#include <vector>
#include <algorithm>
using namespace std;
class Solution {
public:
int minimumTotal(vector<vector<int>>& triangle) {
int n = triangle.size();
vector<int> dp(triangle.back()); // 初始化 dp 为三角形最后一行
// 从倒数第二行向上计算最小路径和
for (int i = n - 2; i >= 0; --i) {
for (int j = 0; j <= i; ++j) {
dp[j] = triangle[i][j] + min(dp[j], dp[j + 1]);
}
}
return dp[0]; // 返回顶部的最小路径和
}
};
Python代码
from typing import List
class Solution:
def minimumTotal(self, triangle: List[List[int]]) -> int:
n = len(triangle)
dp = triangle[-1][:] # 初始化 dp 为三角形最后一行
# 从倒数第二行向上计算最小路径和
for i in range(n - 2, -1, -1):
for j in range(len(triangle[i])):
dp[j] = triangle[i][j] + min(dp[j], dp[j + 1])
return dp[0] # 返回顶部的最小路径和
# 示例调用
triangle = [[2],[3,4],[6,5,7],[4,1,8,3]]
sol = Solution()
print(sol.minimumTotal(triangle)) # 输出: 11
复杂度分析
时间复杂度：O(n2)O(n^2)，其中 nn 是三角形的高度，因为需要遍历每一行和每一个元素。
空间复杂度：O(n)O(n)，使用了一个一维数组
dp来保存当前的最小路径和。
ending
你好呀，我是苍何。是一个每天都在给自家仙人掌讲哲学的执着青年，我活在世上，无非想要明白些道理，遇见些有趣的事。倘能如我所愿，我的一生就算成功。共勉 💪
点击关注下方账号，你将感受到一个朋克的灵魂，且每篇文章都有惊喜。
感谢大家一直以来的阅读、在看和转发，我会把流量主收益都用来发红包，大家可在公众号页面发送相关暗号关键词获取抽奖，每一篇文章会给到一个不同的暗号，对应的抽奖都是独立的，此篇暗号为【美团】，在后台回复【美团】，即可点击进去参与抽奖！抽奖内容、金额、个数等都无变化，在开奖前参与抽奖，操作均有效。
注意，后台（不是评论区，是后台）回复【美团】即可参与抽奖。
后台回复（不是评论区，是后台）即可参与抽奖。后台回复（不是评论区，是后台）即可参与抽奖。
