动态规划是一种求解多阶段决策问题的最优化算法。

一．多阶段决策过程

事件的发展过程分为若干个相互联系的阶段。事件的发展总是初始状态开始，依次经过第一阶段、第二阶段、第三阶段、 …，直至最后一个阶段结束。 如图1所示：

 

图1

二．动态规划术语及性质

为了更好说明问题，我们引入几个术语：

（1）阶段：把所给求解问题的过程恰当地分成若干个相互联系的阶段。如图1所示V1、V2……。值得注意的是，阶段的划分有时候非常直观，因为可能每一步就被划分为一个阶段；但是有时候阶段划分可能就没那么容易了，此时的阶段可能就不是前面所说的“每一步就是一个阶段了”，通常这时候的阶段包含多步，通常每个阶段的步数都不相同。这一点我们后面将举两个例子（分别是上台阶、最大子序列问题）来看看。

（2）状态：通常是指阶段和阶段之间的状态。在动态规划里面，（这个不太确定，只是自己的经验）状态通常包含两个部分，一个是对上一阶段结果的保存；另一个是对下阶段的决策。

（3）决策：就是下一阶段做出什么样的选择。决策的过程主要通过“状态转移方程”体现出来！

（4）动态规划的无后效性：如果给定某一阶段的状态，则在这一阶段以后过程的发展不受这阶段以前各段状态的影响，所有各阶段都确定时，整个过程也就确定了。

（5）动态规划的最优子结构性质：如果问题的最优解成立，那么对于问题的子问题，最优解的子解仍是该子问题的最优解。

（6）状态转移方程：动态规划的核心。设x(k)、x(k+1)为第k、k+1阶段的状态变量，第k阶段的决策结果为u(k)，从第k阶段到k+1阶段的映射为T。则有x(k+1)=T{x(k),u(k)}。

三．动态规划问题的解决过程

（1）正向推进

（2）逆向推进

在两种推进中都可以使用递归等手段来解决。

四．栗子

（1）上台阶问题，题目叙述如图2：

 

代码如下：

###########################
#上楼梯问题
#2016年12月17日
#by:zkj
############################
from numpy import random

def upStairMethods(N):          ##从下到上的方式迭代O(N)
    stairOne = 1; stairTwo = 2; stairN = 0;
    for i in range(3,N+1):
        stairN = stairOne + stairTwo
        stairOne = stairTwo
        stairTwo = stairN
    return stairN

stairCnt = random.randint(3,10) #随机生成楼梯数量
print("楼梯阶数为:\n",stairCnt)
methods = upStairMethods(stairCnt)
print("上楼梯的方法总有:\n",methods)

 （2）最大子序列问题，题目叙述如图3：

代码如下：

####################
#动态规划求最大字段和
#2016.12.13
####################
from numpy import random

def calSubsquence(array,lenth,tupleArray):
    array = list(array)                 ##tuple->list
    
    if max(array) < 0:                  ##动态规划
        return 0
    for i in range(1,lenth):
        if array[i - 1] <= 0:
            array[i] = array[i]
        else:
            array[i] = array[i-1] + array[i]  

    maxIndex = array.index(max(array))  ##找出最大子序列并返回
    if min(array) >= 0:
        return tupleArray
    else:
        for i in range(0,maxIndex+1):
            if min(array[i:maxIndex+1]) >= 0:
                return tupleArray[i:maxIndex+1]
            else:
                i +=1

targetArray = tuple(random.randint(-10,10,10))
print("随机生成的数组为:\n",targetArray)
arrayLenth = len(targetArray)
maxSubsquence = calSubsquence(targetArray,arrayLenth,targetArray)
print("最大子序列为:\n",maxSubsquence,"\n最大子序列之和为:\n",sum(maxSubsquence))