练习题(3) — 另类的动态规划问题

版权声明 本站原创文章 由 萌叔 发表
转载请注明 萌叔 | https://vearne.cc

题目如下:

已知
1) 对于数字1 可以表达为
(1)
2) 对于数字2 可以表达为
(1,1) (2)

解释
1 + 1 = 2

3) 对于数字3 可以表达为
(1,1,1) (1, 2) (2, 1) (3)

1 + 1 + 1 = 3
1 + 2 = 3
2 + 1 = 3

求对于数字N 所有表达项
解法提示:
这是一道比较简单的动态规划问题
对于数字3如果我们把它的所有表达想这样书写

以1为开头的序列的后半部分的和是2
动态规划有两个要素，一个是备忘录，一个是递推公式
我们可以得到如下递推公式
注意：这里的加号和乘号不表示数学意义的加发和乘法
准确的说* 号表示连接，+ 号表示f(n) 的表达项是这些表达项的集合
f (n) = 1 * f(n -1) + 2 * f(n -2) ... ... + (n-1) * f(0)

因此解法如下:
递归解法:

dd = {}  
dd[0] = [[]]  
dd[1] = [[1]]  

def solve(n):  
    if n in dd:  
        return dd[n]  
    else:  
        res = []  
        for i in range(1, n+1):  
            ll = solve(n - i)  
            #clone  
            for item in ll:  
                temp = list(item)  
                temp.insert(0, i)  
                res.append(temp)  
        dd[n] = res  

        return res  

# ---- test ----  
res = solve(2)  
for item in res:  
    print item  

如果仔细思考，我们我们会发现 f(2) 依赖 f(1)，f(3) 依赖f(2) ... f(n) 依赖f(n-1)

可以直接从f(1) , f(2) 一直算到f(n) ， 这样就无需使用递归调用，则性能更好

def solve(n):  
    dd = {}  
    dd[0] = [[]]  
    dd[1] = [[1]]  

    for i in range(1, n + 1):  
        seq = []  
        for j in range(1, i + 1):  
            temp = dd[i - j]  
            for item in temp:  
                s  = list(item)  
                s.insert(0, j)  
                seq.append(s)  
        dd[i] = seq  
    return dd[n]  


# ---- test ----  
res = solve(2)  
for item in res:  
    print item  

print '----------------'  
res = solve(4)  
for item in res:  
    print item