力扣120. 三角形最小路径和

动态规划

• 思路：
  • 假设 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());
    }
};