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 considered as the first word of the next line, or it can be appended to the previous word.
If it is considered as the start of the next line, then dp[i-1] is the badness of the previous line + 500.
If it is appended to the previous word, then dp[i+1] to dp[j] form a line, like:
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