三角形最小路径和
难度：中等
题目描述
给定一个三角形 triangle ，找出自顶向下的最小路径和。
每一步只能移动到下一行中相邻的结点上。相邻的结点 在这里指的是 下标 与 上一层结点下标 相同或者等于 上一层结点下标 + 1 的两个结点。也就是说，如果正位于当前行的下标 i ，那么下一步可以移动到下一行的下标 i 或 i + 1 。
示例1
输入： triangle = [[2],[3,4],[6,5,7],[4,1,8,3]]
输出： 11
示例2
输入： triangle = [[-10]]
输出：-10
题解
是用动态规划
- 当遍历当前行的第一个元素时，该元素位置的最短路径和只能为正上方的最短路径和加当前元素的值；
- 遍历当前行服务器托管网的最后一个元素时，它的最短路径和只能为上方的前一个元素的最短路径和加当前元素的值
- 其余情况下为正上方和左上方的最短路径和的最小值加上当前元素值
动态规划方程为：
d
p
[
i
]
[
j
]
=
{
d
p
[
i
−
1
]
[
j
]
+
t
r
i
a
n
g
l
e
[
i
]
[
j
]
,
j
=
=
0
d
p
[
i
−
1
]
[
j
−
1
]
+
t
r
i
a
n
服务器托管网
g
l
e
[
i
]
[
j
]
,
j
=
=
i
m
i
n
(
d
p
[
i
−
1
]
[
j
−
1
]
,
d
p
[
i
−
1
]
[
j
]
)
+
t
r
i
a
n
g
l
e
[
i
]
[
j
]
,
1
≤
j
dp[i][j]=⎩
⎨
⎧dp[i−1][j]+triangle[i][j],dp[i−1][j−1]+triangle[i][j],min(dp[i−1][j−1],dp[i−1][j])+triangle[i][j],j==0j==i1≤ji
想法代码
class Solution
{
public static void Main(string[] args)
{
Solution solution = new Solution();
IListIListint>> triangles = new ListIListint>>
{
new Listint>{2},
new Listint>{3,4},
new Listint>{6,5,7},
new Listint>{4,1,8,3}
};
int ans = solution.MinimumTotal(triangles);
Console.WriteLine(ans);
}
public int MinimumTotal(IListIListint>> triangle)
{
int[][] dp = new int[triangle.Count][];
for (int i = 0; i triangle.Count; i++)
{
dp[i] = new int[i + 1];
}
dp[0][0] = triangle[0][0];
for (int i = 1; i dp.Length; i++)
{
IListint> t = triangle[i];
for (int j = 0; j dp[i].Length; j++)
{
if (j == 0)
{
dp[i][j] = dp[i - 1][j] + t[j];
}
else if (j == i)
{
dp[i][j] = dp[i - 1][j - 1] + t[j];
}
else
{
dp[i][j] = Math.Min(dp[i - 1][j - 1], dp[i - 1][j]) + t[j];
}
}
}
Array.Sort(dp[dp.Length - 1]);
return dp[dp.Length -1][0];
}
}
服务器托管，北京服务器托管，服务器租用 http://www.fwqtg.net
相关推荐: GaussDB(DWS)基于Flink的实时数仓构建
武汉源创会回归，4月20聊聊大模型” 本文分享自华为云社区《GaussDB(DWS)基于Flink的实时数仓构建》，作者：胡辣汤。 大数据时代，厂商对实时数据分析的诉求越来越强烈，数据分析时效从T+1时效趋向于T+0时效，为了给客户提供极速分析查询能力，华为云…
