动态规划一篇就够了 全网第二详细, 逐步理解, 万字总结

动态规划 - 超详细系列
首先，先大致列下这篇文章会讲到什么
1.相较于暴力解法，动态规划带给我们的是什么？为什么会有重叠子问题以及怎么去避免的?
2.用不同难度的动态规划问题举例说明， 最后会使用《打家劫舍》系列三个题再重温一次.
一、动态规划带给我们的优势
传统递归 vs. DP
1. 先 递归解决
2. 后 动态规划解决
3. 动态规划 + 优化
二、动态规划四大解题步骤处理问题
步骤一：定义dp数组的含义
步骤二：定义状态转移方程
步骤三：初始化过程转移的初始值
步骤四：可优化点(可选)
案例一：打家劫舍I 「来自leetcode198」
步骤一： 定义dp数组的含义
步骤二：找出关系元素间的动态方程
步骤三：初始化数值设定
步骤四：优化
案例二：不同路径「来自leetcode62」
步骤一：定义dp数组的含义
步骤二：找出关系元素间的动态方程
步骤三：初始化数值设定
步骤四：优化
案例三：不同路径II 「来自leetcode63」
步骤一：定义dp数组的含义
步骤二：找出关系元素间的动态方程
步骤三：初始化数值设定
步骤四：优化
案例四：打家劫舍II 「来自leetcode213」
步骤一： 定义dp数组的含义
步骤三：初始化设定
步骤四：优化
案例五：打家劫舍III 「来自leetcode337」
步骤一： 定义dp数组的含义
步骤二：找出关系元素间的动态方程
步骤三：初始化设定

写一个函数，输入n，求斐波那契（Fibonacci）数列的第 n 项。斐波那契数列的定义如下：

F(0) = 0, F(1) = 1
F(N) = F(N - 1) + F(N - 2), 其中 N > 1.
斐波那契数列由 0 和 1 开始，之后的斐波那契数就是由之前的两数相加而得出。

class Solution(object):
    i = 0
    def fib_recur(self, N):
        print "F(",self.i,") = ", N   # 此处仅仅来看递归输出的N
        self.i += 1
        
        if N <= 1:
            return N
        return self.fib_recur(N-1) + self.fib_recur(N-2)  # 递归输出

F( 0 ) =  4
F( 1 ) =  3
F( 2 ) =  2
F( 3 ) =  1
F( 4 ) =  0
F( 5 ) =  1
F( 6 ) =  2
F( 7 ) =  1
F( 8 ) =  0

a. **定义一个一维数组**   --->  一般用dp来命名

b. **动态方程的设定**   --->  题中的F(N) = F(N - 1) + F(N - 2)

c. **初始化数值**   --->  F(0) = 0和F(1) = 1

class Solution(object):
    def fib(self, N):
        if N == 0:
            return 0
     
        dp = [0 for _ in range(N+1)]		# 1定义dp[i]保存第i个计算得到的数值
        dp[0] = 0   	# 2初始化
        dp[1] = 1			# 2初始化
        for i in range(2, N+1):	# 3动态方程实现，由于0和1都实现了赋值，现在需要从第2个位置开始赋值
            dp[i] = dp[i - 1] + dp[i - 2]
       
        print dp		 # 记录计算过程中的次数，与上述递归形成对比
        return dp[N]

[0, 1, 1, 2, 3]
3

顺带将F(1)赋值给dp1， f(2)赋值给dp2

顺带将F(2)赋值给dp1， F(3)赋值给dp2

顺带将F(3)赋值给dp1， F(4)赋值给dp2

class Solution(object):
    def fib_dp1(self, N):
        if N == 0: return 0

        dp1, dp2 = 0, 1

        for i in range(2, N+1):
            dp1 = dp1 + dp2
            dp1, dp2 = dp2, dp1

        return dp2

输入: [1,2,3,1]
输出: 4
解释: 偷窃 1 号房屋 (金额 = 1) ，然后偷窃 3 号房屋 (金额 = 3)。
     偷窃到的最高金额 = 1 + 3 = 4 。

输入: [2,7,9,3,1]
输出: 12
解释: 偷窃 1 号房屋 (金额 = 2), 偷窃 3 号房屋 (金额 = 9)，接着偷窃 5 号房屋 (金额 = 1)。
     偷窃到的最高金额 = 2 + 9 + 1 = 12 。

之前提到的，dp数组存储的值一般代表截止目前的最优值，在该题目中，我们定义：

**dp[i] 代表到达第 i 个房屋偷得的最高金额，也就是当前最大子序和**

无论房屋有几间，最后我们取到dp数组的最后一个值就求得小偷偷得的最高金额

动态规划解决的问题，一般来说就是解决最优子问题，“自顶向下” 的去不断的计算每一步骤的最优值。

也就是想要得到dp[i]的值，我们必须要知道dp[i-1]，dp[i-2]，dp[i-3] ... 的每一步的最优值，在这个状态转移的过程中，我们必须要想清楚怎么去定义关系式。然而在每一步的计算中，都与前几项有关系，这个固定的关系就是我们要寻找的重叠子问题，也同样是接下来要详细定义的动态方程

该题目中，当小偷到达第 i 个屋子的时候，他的选择有两种：一种是偷，另外一种是不偷， 然后选择价值较大者

a. 偷的情况计算：必然是dp[3] = nums[2] + dp[1]，如果是偷取该屋子的话，相邻屋子是不能偷取的，因此，通项式子是：dp[i] =  nums[i-1] + dp[i-2]

b. 不偷的情况计算：必然是dp[3] = dp[2]，如果是不偷取该屋子的话，相邻屋子就是其最优值，因此，通项式子是：dp[i] =  dp[i-1]

最后，要想偷得最高金额，那么，必须选取在偷与不偷之间的最大值作为我们是否选取的关键点。即：

**动态方程:** dp[i] = max(dp[i-1], nums[i-1]+dp[i-2])

初始化: 给没有房子时，dp一个位置，即：dp[0]

	1 当size=0时，没有房子，dp[0]=0；

	2 当size=1时，有一间房子，偷即可：dp[1]=nums[0]

class Solution(object):

    def rob(self, nums):
      # 1.dp[i] 代表当前最大子序和
      # 2.动态方程: dp[i] = max(dp[i-1], nums[i-1]+dp[i-2])
      # 3.初始化: 给没有房子时，dp一个位置，即：dp[0]
      #   3.1 当size=0时，没有房子，dp[0]=0；
      #   3.2 当size=1时，有一间房子，偷即可：dp[1]=nums[0]
      size = len(nums)
      if size == 0:
        return 0

      dp = [0 for _ in range(size+1)]

      dp[0] = 0
      dp[1] = nums[0]
      for i in range(2, size+1):
        dp[i] = max(dp[i-1], nums[i-1]+dp[i-2])
        return dp[size]

从 dp[i] = max(dp[i-1], nums[i-1]+dp[i-2]) 关系来看，每一次动态变化，都与前两次状态有关系（dp[i-1], dp[i-2])，而前面的一些值是没有必要留存的.

所以，dp只需要定义两个变量就好，将空间复杂度降为O(1)	

class Solution(object):

    def rob_o(self, nums):
        # 依照上面的思路，其实我们用到的数据永远都是dp的dp[i-1]和dp[i-2]两个变量
        # 因此，我们可以使用两个变量来存放前两个状态值
        # 空间使用由O(N) -> O(1)

        size = len(nums)
        if size == 0:
            return 0

        dp1 = 0
        dp2 = nums[0]
        for i in range(2, size+1):
            dp1 = max(dp2, nums[i-1]+dp1)
            dp1, dp2 = dp2, dp1
        return dp2

输入: m = 3, n = 2
输出: 3
解释:
从左上角开始，总共有 3 条路径可以到达右下角。

1. 向右 -> 向右 -> 向下
2. 向右 -> 向下 -> 向右
3. 向下 -> 向右 -> 向右

输入: m = 7, n = 3
输出: 28

当前这道题是从左上角到右下角的，题目中规定只能向右或者向下走，所以我们必须要定义一个二维数组来保存计算过程中的值。所以，这块定义：

**dp[i]\[j]: 代表到达位置 (i, j) 的所有路径的总数**

即：机器人从左上角到右下角所有路径的总和，dp中每个位置的值代表行走到达 (i, j) 每个位置的总共的路径数

由于题目中规定只能向右或者向下走，所以在机器人行进的时候，只能是向右或向下.

那么，分别讨论下两种情况，想要到达位置(i, j)，可以从位置(i-1, j)或者(i, j-1)出发到达。因此，到达位置(i, j) 的总的路径数一定是 **到达位置(i-1, j)路径数** + **到达位置(i, j-1)路径数**。那么，现在可以定义动态方程：

**动态方程：dp[i]\[j] = dp[i-1]\[j] + dp[i]\[j-1]**

很明显，在机器人走第 0 行，第 0 列的时候，无论怎么走，都只有 1 种走法。

因此，初始化值的设定，一定是 dp[0..m]\[1] 或者 dp[1]\[0..n] 都等于1

因此初始值如下：

**dp[0] [0….n-1] = 1;**  // 机器人一直向右走，第 0 列统统为 1

**dp[0…m-1] [0] = 1;**  // 机器人一直向下走，第 0 列统统为 1

现在，按照这个思路来整理一下代码

class Solution(object):

    def uniquePaths1(self, m, n):

        # 初始化表格，由于初始化0行 0列都为1。那么，先全部置为1
        dp = [[1 for _ in range(m)] for _ in range(n)]

        for i in range(1, n):
            for j in range(1, m):
                dp[i][j] = dp[i-1][j] + dp[i][j-1]

        return dp[n-1][m-1]

可以依照前面的解决的思路，应该也可以从空间上进行一定的优化

参照前面的案例，之前定义的是一维数组dp，优化点是每一步骤都只与前面的两个计算好的数值有关系，然后优化点就是将dp[N] -> dp1和dp2，空间复杂度由 O(N) -> O(1)，如果是很大规模的数据计算的话，空间效率提升了不少.

现在这个例子中的动态方程是**dp[i]\[j] = dp[i-1]\[j] + dp[i]\[j-1]**，很明显，每一步骤中的状态值只与左边相邻的值和上面的值相关。举例（为了方便，用 3*4 来举例）：

这个完整的图片描述中，机器人从左上角的位置(1, 1)开始移动，逐渐每一步都根据动态方程进行前进，明显的可以看出机器人每移动一格，所得到的路径总和只与它的上方和左方数值有关系。也就是我们会发现，机器人移动到第2行的时候，第0行数据完全是没有用的状态。

因此，这个优化点就出来了，在算法设计的时候，dp仅仅定义2行N列的数组就ok了，省去了m-2行的空间开销。这个代码如果大家想明白了请自行设计出来，自己写出来一定会有更加深刻的理解，再强调：多思考，形成潜移默化的思维方式.

看完这个步骤之后，是不是很明显的优化点，为什么上面没有给出大家代码呢？是因为我看到貌似可以继续优化的点（粘住空间优化项了哈哈哈），那就继续在空间开销上做文章。

**引导：**根据上述咱们的优化方案，说道 "机器人移动到第2行的时候，第0行数据完全是没有用的状态"，其实当前聪明的读者你想想，再看看，下面的图中（从上图截取过来）。 其实，不仅仅是第 0 行完全没用了，而且在第2 行做移动的时候，移动到位置(i, j)的时候，计算好位置(i, j)，那么接下来，位置(i-1, j)的数据也就没用了。换句话说，边走，第 1 行开始的某些数据也就没用了，还在占着空间

**这块大家一定多想想，多理解，多画图**

class Solution(object):

    def uniquePaths2(self, m, n):
        if m > n:
            m, n = n, m

        dp = [1 for _ in range(m)]

        for i in range(1, n):
            for j in range(1, m):
                dp[j] = dp[j] + dp[j-1]

        return dp[m-1]

输入:
[
  [0,0,0],
  [0,1,0],
  [0,0,0]
]
输出: 2
解释:
3x3 网格的正中间有一个障碍物。
从左上角到右下角一共有 2 条不同的路径：

1. 向右 -> 向右 -> 向下 -> 向下
2. 向下 -> 向下 -> 向右 -> 向右

相比于上一题目，相似的是，在机器人走第 0 行，第 0 列的时候，无论怎么走，都只有 1 种走法

但由于有障碍物，那走到障碍物的时候，后面都是走不下去的（下图用第一行来举例）。

所以，初始化第 0 行，第 0 列的时候，障碍物 1 后面的都是不可达的。所以，初始化行和列的逻辑表达：

**该位置是否可达=前一个位置的状态and该位置能否可达 得到能否到达这个位置**

只有前一个位置为1（可达，只有1种方式） ，当前位置为0（无障碍物）这种情况才能到达该位置，然后为该位置设 1 （可达，只有1种方式）

# 0 行初始化表达式: 
obstacleGrid[0][row] = int(obstacleGrid[0][row] == 0 and obstacleGrid[0][row-1] == 1)
# 0 列初始化表达式: 
obstacleGrid[clo][0] = int(obstacleGrid[clo][0] == 0 and obstacleGrid[clo-1][0] == 1)

class Solution(object):

    def uniquePathsWithObstacles1(self, obstacleGrid):
      	# 行列长度
        m = len(obstacleGrid)
        n = len(obstacleGrid[0])

        # 如果在位置(0, 0)，哪里都去不了，直接返回0
        if obstacleGrid[0][0] == 1:
            return 0

        # 否则，位置(0, 0)可以到达
        obstacleGrid[0][0] = 1

        # 初始化 0 列
        for clo in range(1, m):
            obstacleGrid[clo][0] = int(obstacleGrid[clo][0] == 0 and obstacleGrid[clo-1][0] == 1)

        # 初始化 0 行
        for row in range(1, n):
            obstacleGrid[0][row] = int(obstacleGrid[0][row] == 0 and obstacleGrid[0][row-1] == 1)

        # 从位置(1, 1)根据动态方程开始计算
        for i in range(1, m):
            for j in range(1, n):
                if obstacleGrid[i][j] == 0:
                    obstacleGrid[i][j] = obstacleGrid[i-1][j] + obstacleGrid[i][j-1]
                else:
                    obstacleGrid[i][j] = 0

        return obstacleGrid[m-1][n-1]

这块的优化先不谈了，这里基本没有什么优化点，之前都是由于自己要开辟内存空间，通过空间的优化来进行，而本题是在给定的数组中进行操作的

输入: [2,3,2]
输出: 3
解释: 你不能先偷窃 1 号房屋（金额 = 2），然后偷窃 3 号房屋（金额 = 2）, 因为他们是相邻的。

输入: [1,2,3,1]
输出: 4
解释: 你可以先偷窃 1 号房屋（金额 = 1），然后偷窃 3 号房屋（金额 = 3）。
     偷窃到的最高金额 = 1 + 3 = 4 。

dp[i] 代表的含义和之前一致，dp数组存储的值一般代表截止目前的最优值

所以，**dp[i] 代表到达第 i 个房屋偷得的最高金额，也就是当前最大子序和**

但是最后会讨论**不包含首**和**不包含尾**这两种情况下得到的dp数组的最后一位，然后获取其中较大者，就是我们要取得的最高金额

动态方程可参照《打家劫舍I》，有很详细的图解过程，该例子动态方程的变化和之前是完全一致的：

**dp[i] = max(dp[i-1], nums[i-1]+dp[i-2])**

初始化: 给没有房子时，dp一个位置，即：dp[0]

	a. 当size=0时，没有房子，小偷没办法偷：dp[0]=0；

	b. 当size=1时，有一间房子，只要偷即可：dp[1]=nums[0]

由于屋子首位相连接，所以在计算时候，直接分为两种情况。第一种略过第一个屋子，第二种略过第二个屋子，这样得到的两个数组结果。最后只要比较最后一位数值的大小就ok了。解决！

同样从 dp[i] = max(dp[i-1], nums[i-1]+dp[i-2]) 关系来看，每一次动态变化，都与前两次状态有关系（dp[i-1], dp[i-2])，而前面的一些值是没有必要留存的，只要保存两个变量来保存过程最优值就好.

代码中有详细的注释：

class Solution(object):

    def rob(self, nums):
        # 点睛：与打家劫舍I的区别是屋子围成了一个环
        #   那么，很明显可以分为三种情况：
        #   1. 首位都不偷
        #   2. 偷首不偷尾
        #   3. 不偷首偷尾
        # 显然，第1种方式损失太大，选取2、3。
        # 那么，分为两种情况，分别计算不包含首和不包含尾这两种情况来判断哪个大哪个小

        # 1.dp[i] 代表当前最大子序和
        # 2.动态方程: dp[i] = max(dp[i-1] and , nums[i-1]+dp[i-2])
        # 3.初始化: 给没有房子时，dp一个位置，即：dp[0]
        #   3.1 当size=0时，没有房子，dp[0]=0；
        #   3.2 当size=1时，有一间房子，偷即可：dp[1]=nums[0]

        # 依照《打家劫舍I》的优化方案进行计算

        # nums处理，分别切割出去首和去尾的子串
        nums1 = nums[1:]
        nums2 = nums[:-1]

        size = len(nums)
        if size == 0:
            return 0
        if size == 1:
            return nums[0]

        def handle(size, nums):
            dp1 = 0
            dp2 = nums[0]
            for i in range(2, size+1):
                dp1 = max(dp2, nums[i-1]+dp1)
                dp1, dp2 = dp2, dp1
            return dp2

        res1 = handle(size-1, nums1)
        res2 = handle(size-1, nums2)

        return max(res1, res2)

输入: [3,2,3,null,3,null,1]

 		 3
		/ \
   2   3
    \   \ 
     3   1

输出: 7 
解释: 小偷一晚能够盗取的最高金额 = 3 + 3 + 1 = 7.

输入: [3,4,5,1,3,null,1]

 		 3
		/ \
   4   5
  / \   \ 
 1   3   1
输出: 9
解释: 小偷一晚能够盗取的最高金额 = 4 + 5 = 9.

dp[i]代表该节点及以下打最多的劫（拿到最多的钱）

根据我们每走到一个节点，都会有两种情况，那就是 **偷(1)** 与 **不偷(0)**。我们分开来讨论：

a. 用 **dp[0]** 代表不偷取该节点到目前为止拿到最多的钱，那么儿子节点偷不偷都ok。

	所以： **dp[0] = max(left[0], left[1]) + max(right[0], right[1])**

b. 用 **dp[1]** 代表偷了该节点到目前为止拿到最多的钱，则儿子节点都不能被偷。

	所以：**dp[1] = value + left[0] + right[0]**  (value代表该节点的价值)

有看不懂的地方吗？再紧接着解释一下：

	left[0]代表不偷取左孩子拿到最高的金额

	left[1]代表偷取左孩子拿到最高的金额

	right[0]代表不偷取右孩子拿到最高的金额

	right[1]代表偷取右孩子拿到最高的金额

*如果还有不太懂的话，留言或者添加我的公众号「计算广告生态」联系我，随时骚扰我哈*

该例子的初始化比较简单，就是当前树的形状为空的时候，直接返回dp[0, 0]

# Definition for a binary tree node.
class TreeNode(object):
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None


class Solution():

    def rob(self, root):

        # 说明：
        # 1.由于房屋是树状的，因此，我们可以使用遍历树的传统方法进行遍历(前序、中序、后续)
        # 2.简单的思路是，从树低进行往上遍历，拿到最优的打劫值。可以选用后续遍历
        # 3.得到每一节点的最优值，最后选取最优的结果

        # 1.dp[i]代表该节点及以下拿到的最多的钱
        # 2.动态方程：
        #   2.1 dp[0]代表不偷该节点拿到最多的钱，则儿子节点偷不偷都ok。dp[0] = max(left[0], left[1]) + max(right[0], right[1])
        #   2.2 dp[1]代表偷了该节点拿到最多的钱，则儿子节点都不能被偷。dp[1] = var + left[0] + right[0]
        # 3.初始化：当前树的形状为空的时候，直接返回dp[0, 0]
        def postTrasval(root):
            dp = [0, 0]
            if not root:
                return dp
            left = postTrasval(root.left)
            right = postTrasval(root.right)

            dp[0] = max(left[0], left[1]) + max(right[0], right[1])
            dp[1] = root.val + left[0] + right[0]

            return dp

        dp = postTrasval(root)
        return max(dp[0], dp[1])


if __name__ == '__main__':
    # initial tree structure
    T = TreeNode(3)
    T.left = TreeNode(2)
    T.right = TreeNode(3)
    T.left.right = TreeNode(3)
    T.right.right = TreeNode(1)

    # The solution to the Question
    s = Solution()
    print(s.rob(T))