力扣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
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。