题解 | 三角形最小路径和

class Solution {
public:
    int minTrace(vector<vector<int> >& triangle) {
        int n = triangle.size();
        vector<int> dp(n + 1, 0);  // 使用一维dp数组优化空间
        
        // 从底向上
        for(int i = n-1; i >= 0; i--) {
            for(int j = 0; j <= i; j++) {
                dp[j] = min(dp[j], dp[j+1]) + triangle[i][j];
            }
        }
        
        return dp[0];
    }
};

import java.util.*;

public class Solution {
    public int minTrace(int[][] triangle) {
        if (triangle == null || triangle.length == 0) {
            return 0;
        }
        int n = triangle.length;
        int[] dp = new int[n + 1];
        
        // 从底向上
        for (int i = n-1; i >= 0; i--) {
            for (int j = 0; j <= i; j++) {
                dp[j] = Math.min(dp[j], dp[j+1]) + triangle[i][j];
            }
        }
        
        return dp[0];
    }
}

class Solution:
    def minTrace(self, triangle: List[List[int]]) -> int:
        n = len(triangle)
        dp = [0] * (n + 1)
        
        # 从底向上
        for i in range(n-1, -1, -1):
            for j in range(i + 1):
                dp[j] = min(dp[j], dp[j+1]) + triangle[i][j]
                
        return dp[0]