每日leetcode第0036天 0120. Triangle

这道题也是一道动态规划的题目。

在1994年的ioi国际信息学奥林匹克竞赛中出场,现在的oier来说,这已经是一道简单题了。

他像是昨天那道走格子求最少路费,又结合了前几天的帕斯卡三角那种三角形形式的题目。

初始化、状态转移方程式就是帕斯卡三角的改进版,循环公式和帕斯卡三角那题如出一辙。

最后输出前要记得遍历最底下一行,找出最小值,而不是输出最后一个点。

初始化initialization:
min_sums[0][0] = triangle[0][0];
for (int i = 1; i < n; ++i) {
min_sums[i][0] = min_sums[i-1][0] + triangle[i][0];
min_sums[i][i] = min_sums[i-1][i-1] + triangle[i][i];
}

状态转移方程式optimum-value function:
min_sums[i][j] = min(min_sums[i-1][j-1], min_sums[i-1][j]) + triangle[i][j];

循环公式recurrent formula:
for (int i = 1; i < n; ++i) {
for (int j = 1; j < i; ++j) {
}
}

 



关于樊轶群

一个善良的理想主义者。
此条目发表在每日LeetCode分类目录,贴了, 标签。将固定链接加入收藏夹。

发表评论

您的电子邮箱地址不会被公开。