Found another online solution. However, it cannot pass the OJ here. The reason is that this solution optimize the variation of number of spaces of each line. The leetcode question is to fit as many string as possible. Does this solution make sense to you guys? Any comments would be welcomed.

public class Solution {
public List<String> fullJustify(String[] words, int width) {
int cost[][] = new int[words.length][words.length];
List<String> res = new ArrayList<>();
for(int i=0 ; i < words.length; i++){
cost[i][i] = width - words[i].length();
for(int j=i+1; j < words.length; j++){
cost[i][j] = cost[i][j-1] - words[j].length() - 1;
}
}
for(int i=0; i < words.length; i++){
for(int j=i; j < words.length; j++){
if(cost[i][j] < 0){
cost[i][j] = Integer.MAX_VALUE;
}else{
cost[i][j] = (int)Math.pow(cost[i][j], 2);
}
}
}
int minCost[] = new int[words.length];
int result[] = new int[words.length];
for(int i = words.length-1; i >= 0 ; i--){
minCost[i] = cost[i][words.length-1];
result[i] = words.length;
for(int j=words.length-1; j > i; j--){
if(cost[i][j-1] == Integer.MAX_VALUE){
continue;
}
if(minCost[i] > minCost[j] + cost[i][j-1]){
minCost[i] = minCost[j] + cost[i][j-1];
result[i] = j;
}
}
}
int i = 0;
int j;
do{
j = result[i];
StringBuilder builder = new StringBuilder();
for(int k=i; k < j; k++){
builder.append(words[k] + " ");
}
res.add(builder.toString());
i = j;
}while(j < words.length);
return res;
}
}