本文以两个具体例子详细剖析动态规划算法设计思想，主要参考圣经《算法导论》，加上自己的一些理解，主要是附上了一些具体实现过程，所以希望能对大家有所帮助。

#_*_ coding:utf-8 _*_

import numpy as np

def MemoizedCutRodAux(p,n,r,s):

    if r[n]>=0:

        return r[n]

    if n==0:

        q=0

        c=0

    else:

        q=-1

        c=-1

        for i in range(1,n+1):

            if q<(p[i]+MemoizedCutRodAux(p,n-i,r,s)):

                q=p[i]+MemoizedCutRodAux(p,n-i,r,s)

                c=i

    r[n]=q

    s[n]=c

    return q

def MemoizedCutRod(p,n):

    r=-np.ones(n+1)

    s = -np.ones(n + 1)

    MemoizedCutRodAux(p,n,r,s)

    return r,s

if __name__=='__main__':

    p=np.array([0,1,5,8,9,10,17,17,20,24,30])

    r,s=MemoizedCutRod(p, 10)

    print r

    print s

 

结果输出：

r=[  0.   1.   5.   8.  10.  13.  17.  18.  22.  25.  30.]

s=[  0.   1.   2.   3.   2.   2.   6.   1.   2.   3.  10.]

import numpy as np

def BottomUpCutRod(p,n):

    r = -np.ones(n + 1)

    s = -np.ones(n + 1)

    r[0]=0

    s[0]=0

    q=-1

    for j in range(1,n+1):

        for i in range(1,j+1):

            if q<(p[i]+r[j-i]):

                q=p[i]+r[j-i]

                s[j]=i

        r[j]=q

    return r,s

if __name__=='__main__':

    p = np.array([0, 1, 5, 8, 9, 10, 17, 17, 20, 24, 30])

    r,s= BottomUpCutRod(p,10)

    print r

    print s

★步骤三：采用自底向上迭代法计算最优解的值

import numpy as np

def MatrixChain(p):

    n=p.size-1

    m=np.ones((n+1,n+1))*np.inf

    s = np.zeros((n+1, n+1))

    for i in range(n+1):

        m[i,i]=0

    for lenth in range(2,n+1):