Word Wrap via Dynamic Programming

Question

Word Wrap problem in short:

Given n words and a line length, break the words into lines in such a manner that minimizes the sum of the costs of all the lines. Consider the cost of each line being (free space in the line)^2.

I'm supposed to implement an algorithm with \$O(n)\$ time complexity and \$O(n^2)\$ space complexity. The way I see mine is \$O(n^2)\$ in time and \$O(n^3)\$ in space, but when looking for better solutions I found people describing the same procedure I followed as \$O(n)\$ and \$O(n^2)\$. For example, here and in the full description of the problem linked above.

Are they simply ignoring the cost of calculating the penalty cost of each line (they call it "badness" and I "cost")? Because inside their main \$O(n^2)\$ loop they call the badness function that contains a \$O(n)\$ loop inside. Am I supposed to take into account only the cost of the dynamic programming part? If not, what am I doing effectively different? How could I improve it?

using namespace std;

// all vectors start to be filled in 1
void solve(vector<string> words, int line_width){
    int i, j, k;
    int n = words.size() - 1;  // number of words
    int opt[n+1]; // opt[j] = min cost for a text ending in words[j]
    int cost[n+1][n+1]; // cost[i][j] cost of adding a line from words[i] to words[j]
    int parent[n+1]; // parent[j] = i means that the optimal line ending in j starts in i

    // fills cost  
    for(i = 1; i <= n; ++i){
        for(j = i; j <= n; ++j){
            int filled = j-i; // number of spaces added between words i and j
            for(k = i; k <= j; ++k){
                filled += words[k].length(); 
            }
            if(filled > line_width){ 
                cost[i][j] = INF; // if such a line is not possible
            } else {
                cost[i][j] = (line_width - filled) * (line_width - filled);
            }   
        }
    }

    // fills opt
    opt[0] = 0;
    for(j = 1; j <= n; ++j){
        opt[j] = INF;
        for(i = 1; i <= j; ++i){
            if(opt[i-1] + cost[i][j] < opt[j]){ 
                opt[j] = opt[i-1] + cost[i][j];
            }
        }
    }

    // prints solution backwards (because of the order 'parent' was filled)
    int end = n; 
    string solution = "";
    while(end > 0){
        solution = words[end] + '\n' + solution; 
        for(i = end - 1; i >= parent[end]; --i){
            solution = words[i] + ' ' + solution;
        }
        end = parent[end] - 1;
    }
    cout << solution;
}