木又连续日更第20天(20/138)
木又的第160篇leetcode解题报告
动态规划
类型第5篇解题报告
leetcode第120题:三角形最小路径和
https://leetcode-cn.com/problems/triangle/
【题目】
给定一个三角形,找出自顶向下的最小路径和。每一步只能移动到下一行中相邻的结点上。
例如,给定三角形:
[ [2], [3,4], [6,5,7], [4,1,8,3] ] 自顶向下的最小路径和为 11(即,2 + 3 + 5 + 1 = 11)。
说明:
如果你可以只使用 O(n) 的额外空间(n 为三角形的总行数)来解决这个问题,那么你的算法会很加分。
【思路】
典型的动态规划题,dp长度会变化,建议j == 0时进行插入操作,方便后续处理。
递推公式为:
j == 0时,最小值只可能来自dp[0],dp.insert(0, dp[0] + triangle[i][0])
j == len(triangle[i]) - 1时,最小值只可能来自dp[-1],dp[j] += triangle[i][j]
其他情况,最小值来自dp[j]和dp[j+1],dp[j] = min(dp[j], dp[j+1]) + triangle[i][j]
【代码】
python版本
class Solution(object):
def minimumTotal(self, triangle):
"""
:type triangle: List[List[int]]
:rtype: int
"""
if not len(triangle):
return 0
dp = [triangle[0][0]]
for i in range(1, len(triangle)):
for j in range(len(triangle[i])):
if j == 0:
dp.insert(0, dp[0] + triangle[i][j])
elif j == len(triangle[i]) - 1:
dp[j] += triangle[i][j]
else:
dp[j] = min(dp[j], dp[j+1]) + triangle[i][j]
return min(dp)
C++版本
class Solution {
public:
int minimumTotal(vector<vector<int>>& triangle) {
if(triangle.size() == 0 || triangle[0].size() == 0)
return 0;
vector<int> dp;
dp.push_back(triangle[0][0]);
for(int i=1; i < triangle.size(); i++){
// 首尾元素,直接+dp首尾元素
// 其他元素,找到dp相邻元素最小值,再相加
dp.insert(dp.begin(), dp[0] + triangle[i][0]);
for(int j=1; j < triangle[i].size(); j++){
if(j == triangle[i].size() - 1)
dp[j] += triangle[i][j];
else
dp[j] = min(dp[j], dp[j+1]) + triangle[i][j];
}
}
// 取得最小值
int res = INT_MAX;
for(auto num: dp)
if(num < res)
res = num;
return res;
}
};
前一篇文章:T159-爬楼梯