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 1void 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;}
Word Wrap via Dynamic Programming
c++;complexity;dynamic programming