dp[i] represents the minimum badness when a line ends with the i-th word.
dp[i] = min{dp[i-1]+500,dp[j]+badness
(Reference: http://www.cnblogs.com/staginner/archive/2011/12/07/2279059.html)
So dp[i] can be treated as the first word of the next line
or it can be treated as following another word.
If it is treated as the start of the next line, then dp[i-1] is the previous line + 500
If it is treated as following another word, dp[i+1] to dp[j] form a line
which is
this___________ <=dp[1] 500
this__________is <=dp[2]
this___is____best <=dp[3]
Then compare dp[2] with dp[1]
this___________
is____________ dp[2]
this___________
is_____best____ dp[3]
this___________
is____________
best___________ dp[3]
//
// GGGGGGGGGGGGG CCCCCCCCCCCCC AAA
// GGG::::::::::::G CCC::::::::::::C A:::A
// GG:::::::::::::::G CC:::::::::::::::C A:::::A
// G:::::GGGGGGGG::::G C:::::CCCCCCCC::::C A:::::::A
// G:::::G GGGGGG C:::::C CCCCCC A:::::::::A
//G:::::G C:::::C A:::::A:::::A
//G:::::G C:::::C A:::::A A:::::A
//G:::::G GGGGGGGGGGC:::::C A:::::A A:::::A
//G:::::G G::::::::GC:::::C A:::::A A:::::A
//G:::::G GGGGG::::GC:::::C A:::::AAAAAAAAA:::::A
//G:::::G G::::GC:::::C A:::::::::::::::::::::A
// G:::::G G::::G C:::::C CCCCCC A:::::AAAAAAAAAAAAA:::::A
// G:::::GGGG