I think there is something wrong...


  • 0
    B

    For the example test case, my code runs correctly on my machine, I can't figure out why oj thinks my return is 10 instead of 11?

    #include <iostream>
    #include <vector>
    using namespace std;
    
    class Solution {
        void printVec(const vector<int> &v) {
            for (int i = 0; i < v.size(); ++i) {
                cout << v[i] << " ";
            }
            cout << endl;
        }
    public:
        int minimumTotal(vector<vector<int> > &triangle) {
            vector<int> s(triangle[triangle.size()-1].size(), triangle[0][0]);
            for (int row = 1; row < triangle.size(); ++row) {
                vector<int> newS(triangle[row].size(), 0);
                for (int i = 0; i < triangle[row].size(); ++i) {
                    int pre_row = row-1;
                    bool has_set_min = false;
                    int preMinSum;
                    for (int j = i-1; j <= i; ++j) {
                        if (j >= 0 && j < triangle[pre_row].size()) {
                            if (!has_set_min) {
                                preMinSum = s[j];
                                has_set_min = true;
                            } else {
                                if (preMinSum > s[j])
                                    preMinSum = s[j];
                            }
                        }
                    }
                    newS[i] = preMinSum + triangle[row][i];
                }
                for (int i = 0; i < triangle[row].size(); ++i) {
                    s[i] = newS[i];
                }
                //printVec(s);
            }
            bool has_set_min = false;
            int minSum;
            for (int i = 0; i < s.size(); ++i) {
                if (has_set_min) {
                    has_set_min = true;
                    minSum = s[i];
                } else {
                    if (s[i] < minSum)
                        minSum = s[i];
                }
            }
            return minSum;
        }
    };
    
    int main() {
        int a1[1] = {2};
        int a2[2] = {3,4};
        int a3[3] = {6,5,7};
        int a4[4] = {4,1,8,3};
        vector<vector<int> > input(4);
        input[0] = vector<int>(a1, a1+1);
        input[1] = vector<int>(a2, a2+2);
        input[2] = vector<int>(a3, a3+3);
        input[3] = vector<int>(a4, a4+4);
        Solution sol;
        int min = sol.minimumTotal(input);
        cout << "solution: " << min << endl;
        return 0;
    }

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.