放好前i个词后,前i个词对后面的词的影响只与第i个词前的空格数有关
也就是满足无后效性
那么用f[i][j]表示放好前i个词,且第i个词前有j个空格的最小代价
那么可以有这样的推导:

f[i+1][j] = 
Min{f[i][k] + (第i个词前有k个空格,与第i+1个词前有j个空格所产生的代价)}
(其中k 取遍 1..n-strlen(word[i]))
这样算出所有的f[i][j]
那么:
ans = Min{f[n][i]}(i取遍1..n-strlen(n))
就是我们要找的答案
> 用某i个，第j个在最后的数作状态  这句话什么意思？？

• 这样DP之前要不要枚举全排列啊? (0) yiyiyi4321 2006-07-27 16:49:10
  • 不是 (0) sunmoonstar_love 2006-07-27 16:58:50
    • 多数情况下要枚举二进制 (0) sunmoonstar_love 2006-07-27 17:00:21
  • 这叫枚举不叫dp (0) wywcgs 2006-07-27 16:59:14
    • 感觉这样只做一次不能得出最优解,是不是我哪里理解错了? (0) yiyiyi4321 2006-07-27 17:03:57
• f[i][j],i表示序列被选择的状态吧,总算明白了 (19) yiyiyi4321 2006-08-02 13:21:30