DP原理是令p[i]为s[i : n-1]的最优解,初始化为p[n]=0,转移公式为:

p[i]=max( freq(s[i : i+k-1] ) + p[i+k] )        1<=k<=n-i

代码如下:

update at 2011.5.12: 使用了defaultdict简化了代码

# coding: utf-8
 
import collections
d=collections.defaultdict(lambda:0)
 
def init(dictfile):
    f=open(dictfile,'r')
    while 1:
        line=f.readline()
        if not line: break
        word, freq = line.split('\t')
        d[word.decode('gbk')]=int(freq)
    f.close()
 
def fenci(s):
    l=len(s)
    p=[0 for i in range(l+1)]
    t=[1 for i in range(l)]
    for i in range(l-1,-1,-1):
        for k in range(1,l-i+1):
            if(d[s[i:i+k]]+p[i+k] > p[i]):
                p[i]=d[s[i:i+k]]+p[i+k] 
                t[i]=k
    print 'sum:',p[0]
    i=0
    while i<l:
        print s[i:i+t[i]].encode('utf8'), # 'gbk' for win
        i=i+t[i]
 
 
if __name__ == '__main__':
    init('dict.txt')
    s="科学研究需要大量的资金但社会资源有限需要政府调控所以需要政府的限制"
    s=s.decode('utf8')
    fenci(s)

显示结果为:

sum: 33505
科学 研究 需要 大量 的 资金 但 社会 资源 有限 需要 政府 调控 所以 需要 政府 的 限制

顺便贴一个以前写的求拼音首字母的小脚本:

# coding: utf-8
 
a=[ i.decode('utf8').encode('gbk') for i in
     ['澳', '怖', '错', '堕', '贰', '咐', '过',
      '祸', '祸', '骏', '阔', '络', '穆', '诺',
      '沤', '瀑', '群', '弱', '所', '唾',
      '唾', '唾', '误', '褕', '孕', '座',] ]
 
def firstpy(s):
    s=s.encode('gbk')
    i=0
    while i<26 and a[i]<s:
        i+=1
    return '%c' % (97+i)
 
if __name__=='__main__':
    s='判断字符串首字母'.decode('utf8')
    for i in range(len(s)):
        print firstpy(s[i]),