力扣120. 三角形最小路径和
2023-12-14 04:57:22
动态规划
- 思路:
- 假设 dp[i][j] 为最小路径到第 i 层的第 j 个元素的值;
- 则 dp[i][j] = min(dp[i - 1][j - 1], dp[i - 1][j]) + tr[i][j];
- 当 j = 0 时,dp[i][j] = dp[i - 1][0] + tr[i][0];(可以认为 j - 1 不能越界,实际意义是最左边元素上一层路由来自最左边)
- 当 j = i 时,(已知第 i 层有 i + 1 个元素,i 从 0开始),上一层没有第 i 个元素;如果最小路径最后一个节点是 tr[i][i] ,只能从上一层的 tr[i - 1][i - 1]路由,即
- dp[i][i] = dp[i - 1][i - 1] + tr[i][i]
- 边界条件:dp[0][0] = tr[0][0]
class Solution {
public:
int minimumTotal(vector<vector<int>>& triangle) {
int size = triangle.size();
std::vector<std::vector<int>> dp(size, std::vector<int>(size));
dp[0][0] = triangle[0][0];
for (int i = 1; i < size; ++i) {
dp[i][0] = dp[i - 1][0] + triangle[i][0];
for (int j = 1; j < i; ++j) {
dp[i][j] = std::min(dp[i - 1][j - 1], dp[i - 1][j]) + triangle[i][j];
}
dp[i][i] = dp[i - 1][i - 1] + triangle[i][i];
}
return *std::min_element(dp[size - 1].begin(), dp[size - 1].end());
}
};
文章来源:https://blog.csdn.net/N_BenBird/article/details/134985362
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。 如若内容造成侵权/违法违规/事实不符,请联系我的编程经验分享网邮箱:veading@qq.com进行投诉反馈,一经查实,立即删除!
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。 如若内容造成侵权/违法违规/事实不符,请联系我的编程经验分享网邮箱:veading@qq.com进行投诉反馈,一经查实,立即删除!