动态规划

¶定义

¶官方定义

动态规划算法是通过拆分问题，定义问题状态和状态之间的关系，使得问题能够以递推(或者分治)的方式解决。

动态规划算法的基本思想和分治法类似，也是将带求解的问题分为若干个子问题，按顺序求解各个子问题的解，前一个子问题的解为后一个子问题的解提供了有用的信息。在求解任一子问题时，列出各种可能的局部解，通过策略保留那些可能达到最优的局部解，丢弃其他局部解。以此解决各个子问题，最后一个子问题就是初始问题的解。

¶基本思想与策略编辑

由于动态规划解决的问题多数有重叠的子问题这个特点，为了减少重复计算，对每一个子问题只解一次，将其不同阶段的不同状态保存在一个二维数组中。

上述内容解释：

对于拆分问题：个人理解就是根据问题的可能性把问题划分成一步一步这样就可以通过递推或者递归来实现
对于定义问题状态和状态之间的关系：个人理解是前面拆分的步骤之间的关系，是以一种量化的形式表现出来的，类似于，高中学的推导公式，因为这种式子很容易用程序写出来（也就是常说的状态转移方程）
对于定义最后的话，个人理解是在我们找到最优解之后，需要将它保存下来，为了能够在后一步求解下一个子问题时，使用到前一步的最优解，在这个过程中难免有一些相比于最优解差的解，此时我们应该放弃，只保存最优解。

多说无益，折断的骨头，才是最好的课本（实战学习最能帮助理解了）

¶经典动态规划——数字三角问题

题目：

figure.1

在上面的数字三角形中寻找一条从顶部到底部的路径，使得路径上所经过的数字之和最大。路径上的每一步只能往左下或者右下走。只需要求出这个最大和即可，附加：如果可以的话也可以给出路径。(三角形的行数大于1小于等于100，数字为0-99)

输入：
    7
    3 8
    8 1 0
    2 7 4 4
    4 5 2 6 5

将上面的等腰三角形转换成了直角三角形，方便存储输入，很明显可以看出可以使用5×5的数组存储，没有数字的部分使用-1填充

对于上述输入，我们尽可以采用向下或者向右下两种选择方式，最后一行则作为边界条件。
很容易我们想到可以使用递归来解决该问题，因为每一步不是向右下就是向下走，下面是Python递归方法的代码：

class dynamic_progam():
    def MaxSum(self,D, i ,j, n):
        """
        :type D: list  matrix
        :type i: int  horizontal
        :type j: int  ordinate
        :type n: int  stop line
        :rtype : int
        """
        if i == n:
            return D[i][j]
        x = self.MaxSum(D,i+1,j,n) # 向下移动
        y = self.MaxSum(D,i+1,j+1,n) #向右下移动
        return  max(x,y)+D[i][j]

观察上面代码，我们可以发现仅通过这种递归的方法，我们会将所有的路径都遍历一遍(DFS)，这其中存在了大量的重复计算，当行数很大的时候就会超时，如果每算出一个maxSum(i,j)，就将让他保存起来，下次用到它的值时直接取用，则可以免去重复计算，那么就可以大大的缩短计算复杂度。

代码：
class dynamic_progam():
    global maxsum # 存储最大值的全局数组  初始全为-1
    def MaxSum(self,D, i ,j, n):
        """
        :type D: list  matrix
        :type i: int  horizontal
        :type j: int  ordinate
        :type n: int  stop line
        :rtype : NULL
        """
        if maxsum[i][j] != -1:
            return
        if i == n:
            maxsum[i][j] =  D[i][j]
        else:
            x = self.MaxSum(D, i + 1, j, n)  # 向下移动
            y = self.MaxSum(D, i + 1, j + 1, n)  # 向右下移动
            maxsum[i][j] = max(x,y) + D[i][j] # 存储信息
        return

¶经典动态规划——背包问题

在N件物品取出若干件放在容量为W的背包里，每件物品的体积为W1, W2, …, Wn (Wi为整数)，与之相对应的价值分别为P1, P2, …,Pn(Pi为整数)，求背包能够容纳的最大价值。

该问题是很明显的贪心问题, 分别

# 背包问题
    ## dp存储数组, 该数组横坐标表示从第一个物品开始放到第几个物品，纵坐标代表背包还有多少容量，dp[i][j]的值代表当前背包的价值为多少
    global dp
    def bagProblem(self, n, v, w, p):
        """
        :type n: int 横坐标表示从第一个物品开始放到第几个物品
        :type v: int 纵坐标代表背包还有多少容量
        :type w: list 每个物品对应的体积
        :type p: list 每个物品对应的价值
        """
        for i in range(1,n+1):
            for j in range(1,v+1):
                if j >= w[i]:
                    # 能放下该物品，则减去空间，增加价值，并和不放该物品前的价值比较大小，取大小
                    dp[i][j] = max(dp[i-1][j],dp[i-1][j-w[i]]+p[i])
                else:
                    # 如果放不下，则存为上一个物品之后的价值
                    dp[i][j] = dp[i-1][j]
        
        return dp

¶解题思路

首先拿到一个问题，要先考虑是否可以拆分成多个子问题求解，将问题刻画成一个个子问题后，然后在考虑使用递归来解决(类似分治)，最后再将递归转换为动态规划求解。
递归转换为动态规划的一般方法：
如果该递归函数有n个参数, 那么就定义一个n维数组, 数组下标示递归函数参数的取值范围(也就是数组每一维的大小)，数组元素的值是递归函数的返回值(初始化为一个标志值，表示还未被填充)，这样就可以从边界值开始逐步填充数组，相当于计算递归函数的逆过程。

ps：一般遇到求最优解可拆分问题都适合用动态规划求解。