P208. 三角形中的最小路径和

https://algocasts.io/episodes/M0G2MOmz

通过自底向上计算路径和的时候,是不是可以直接在原数组上修改,而不需要额外的空间呢?

int minimumTotal(vector<vector<int>>& triangle) {
        int len = triangle.size();
        for (int i = len - 2; i >= 0; i--) {
            for (int j = 0; j <= i; j++) {
                triangle[i][j] += min(triangle[i+1][j], triangle[i+1][j+1]);
            }
        }
        return triangle[0][0];
}

@Riki

可以。但对于是否修改输入数据,我推荐的原则是:

除非题目有明确的空间复杂度限制,迫使你不得不去修改输入数据才能达到这个空间复杂度要求,否则一律不建议修改输入数据。