[站外图片上传中...(image-fe2902-1583294261806)]
什么是动态规划？
动态规划（Dynamic programming，简称DP），是一种通过“大而化小”的思路解决问题的算法。
动态规划没有明确的算法模板，准确的说，它是一种思想。动态规划是一种解决问题的思想。
什么样的题目适用于动态规划
- 求最大值 / 最小值
- 求可不可行
- 求方案总数
以上三种问题基本上都是用动态规划来求解。
注意：如果问题是让你求出“所有的”方案和结果，则肯定不是使用动态规划。
动态规划问题的解决过程
主要以3个子目标来攻克此类问题：
- 建立状态转移方程。
- 缓存并复用以往结果。
- 按顺序从小往大算。
举个简单的例子，1个人有2条腿，2个人有4条腿，...，100 个人有多少条腿？
首先要建立状态转移方程： f(n) = 2n
这个太简单了不用缓存复用，直接计算即可。
嘴上说还是不够的，我们用实际的问题从浅到深，逐步来深入了解动态规划问题。
[Talk is cheap. Show me the code]
一、斐波那契数列
斐波那契数列：0，1，1，2，3，5，8，13，21，34，55，89，144...
图形如下：
[图片上传失败...(image-cea13e-1583294261806)]
- 斐波那契数列规律计算公式如下：
[图片上传失败...(image-208a66-1583294261806)]
- 先看看暴力递归方法：
def fib(n):
if n < 2:
return n
else:
return fib(n - 1) + fib(n - 2)
if __name__ == "__main__":
result = fib(100)
print(result) # 别等了 根本执行不出来
简单递归的时间复杂度达到了O(n2)。 因为每次都要进行重复计算。
f(3) = f(2) + f(1)
f(4) = f(3) + f(2)
可以看出，f(2) 计算了两次，计算的n越大，循环的次数越多。
-
动态规划
In [20]: def fib(n): ...: result = list(range(n+1)) # 用于缓存以往结果，以便复用（目标2） ...: for i in range(n + 1): # 按顺序从小往大算（目标3） ...: if i < 2: ...: result[i] = i ...: else: # 使用状态转移方程（目标1），同时复用以往结果（目标2） ...: result[i] = result[i - 1] + result[i - 2] ...: return result[-1] # 输出列表中最后一个数值，也就是fib(n)的值 ...: In [21]: result = fib(100) In [22]: result Out[22]: 354224848179261915075L
- （目标1）状态转移方程是什么: f(n) = f(n-1) + f(n-2)
- （目标2）缓存并复用以往的结果。在
result[i]=result[i - 1]+result[i - 2]中进行了复用。相当于你在计算了 + 1 + 1 + 1 + 1 + 1 + 1 + 1= 7 之后，再 + 1 你可以很快的计算出是 8 ，不必再重新将 8 个 1 相加。 - （目标3）从小到大计算。这样以来，时间复杂度降为
O(n)。我们只需要计算红圈圈出的部分即可。节省了大量的时间。
二、不同路径问题
参照LeetCode上的62. 不同路径
一个机器人位于一个 m x n 网格的左上角 （起始点在下图中标记为“Start” ）。
机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为“Finish”）。
问总共有多少条不同的路径？
上图是一个7 x 3 的网格。有多少可能的路径？
太多了，我简化一个3 X 2 的。
解这道题的时候，我们也要从三个目标开始
-
（目标1）状态转移方程是什么:
这道题你必须要知道转移方程是什么。不然的话下面都不用做了...
f(i, j) = f(i-1, j) + f(i, j - 1) （目标2）缓存并复用以往的结果。这里是一个二维的行列问题。我在这里用二维的数组解决这个问题。
（目标3）同样也是从小到大计算。我们需要双重循环，逐行逐列进行计算。
# encoding:utf8
class Solution(object):
def uniquePaths(self, m, n):
"""
:type m: int m为行数
:type n: int n为列数
:rtype: int
"""
result = [[1] * n] * m
for i in range(1, m):
for j in range(1, n):
result[i][j] = result[i][j - 1] + result[i - 1][j]
return result[-1][-1]
if __name__ == '__main__':
s = Solution()
print s.uniquePaths(3, 7)
输出结果为28，证明我们的计算方法是正确的。
三、01背包问题
有n个物品，它们有各自的体积和价值，现有给定容量的背包，如何让背包里装入的物品具有最大的价值总和？
为方便讲解和理解，下面讲述的例子均先用具体的数字代入，即：eg：number＝4，capacity＝6
| i（物品编号） | 1 | 2 | 3 | 4 |
|---|---|---|---|---|
| w（体积） | 2 | 3 | 4 | 5 |
| v（价值） | 3 | 4 | 5 | 6 |
背包问题(0—1背包)
有N件物品，背包的最大承重为M，每件物品的数量均为1，价值集合为V，重量集合为W，计算该背包可以承载的物品的最大价值。
动态规划思想：
动态规划解题步骤：问题抽象化、建立模型、寻找约束条件、判断是否满足最优性原理、找大问题与小问题的递推关系式、填表、寻找解组成
-
动态规划的原理：
- 动态规划与分治法类似，都是把大问题拆分成小问题，通过寻找大问题与小问题的递推关系，解决一个个小问题，最终达到解决原问题的效果。
- 但不同的是：
- 分治法在子问题和子子问题等上被重复计算了很多次，
- 而动态规划则具有记忆性，通过填写表把所有已经解决的子问题答案纪录下来，在新问题里需要用到的子问题可以直接提取，避免了重复计算，从而节约了时间，所以在问题满足最优性原理之后，用动态规划解决问题的核心就在于填表，表填写完毕，最优解也就找到。
-
背包问题的解决过程
在解决问题之前，为描述方便，首先定义一些变量：Vi表示第i个物品的价值，Wi表示第i个物品的体积，定义V(i,j)：当前背包容量j，前i个物品最佳组合对应的价值，同时背包问题抽象化（X1，X2，…，Xn，其中Xi取0或1，表示第i个物品选或不选）。此处要注意各个变量代表的含义，尤其是
V(i,j)：当前背包容量j，前i个物品最佳组合对应的价值。
1、建立模型，即求max(V1X1+V2X2+…+VnXn)；
2、寻找约束条件，W1X1+W2X2+…+WnXn < capacity；
3、寻找递推关系式，面对当前商品有两种可能性：
图示：
| capacity | 0 | 1 | 2 | 3 | 4 | 5 | 6 | ||
|---|---|---|---|---|---|---|---|---|---|
| 0 | weight | value | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| 1 | 2 | 3 | 0 | 0 | 3 | 3 | 3 | 3 | 3 |
| 2 | 3 | 4 | 0 | 0 | 3 | 4 | 4 | 7 | 7 |
| 3 | 4 | 5 | 0 | 0 | 3 | 4 | 5 | 7 | 8 |
| 4 | 5 | 6 | 0 | 0 | 3 | 4 | 5 | 7 | 8 |
# encoding:utf8
class Solution(object):
def bag01(self, weights, values, capacity):
# 动态规划
n = len(weights)
result = [[0 for j in range(capacity + 1)] for i in range(n + 1)]
for i in range(1, n + 1):
for j in range(1, capacity + 1):
result[i][j] = result[i - 1][j]
# 背包总容量够放当前物体，遍历前一个状态考虑是否置换
if j >= weights[i - 1] and result[i][j] < result[i - 1][j - weights[i - 1]] + values[i - 1]:
result[i][j] = result[i - 1][j - weights[i - 1]] + values[i - 1]
for x in result:
print(x)
return result
def show(self, weights, capacity, result):
n = len(weights)
print ('最大解为：{}'.format(result[n][capacity]))
x = [False for i in range(n + 1)]
j = capacity
for i in range(n, 0, -1):
if result[i][j] > result[i - 1][j]:
# i代表第i个物品，如果放入第i个物品的价值大于同等重量放入i-1物品的重量，说明选择了物品i
x[i] = True
j -= weights[i - 1]
print('items:')
for i in range(n + 1):
if x[i]:
print('no:{}'.format(i))
if __name__ == '__main__':
s = Solution()
weights = [2, 2, 3, 1, 5, 2]
values = [2, 3, 1, 5, 4, 3]
capacity = 10
result = s.bag01(weights, values, capacity)
s.show(weights, capacity, result)
输出结果：
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
[0, 0, 2, 2, 2, 2, 2, 2, 2, 2, 2]
[0, 0, 3, 3, 5, 5, 5, 5, 5, 5, 5]
[0, 0, 3, 3, 5, 5, 5, 6, 6, 6, 6]
[0, 5, 5, 8, 8, 10, 10, 10, 11, 11, 11]
[0, 5, 5, 8, 8, 10, 10, 10, 12, 12, 14]
[0, 5, 5, 8, 8, 11, 11, 13, 13, 13, 15]
最大解为：15
items:
no:2
no:4
no:5
no:6
Process finished with exit code 0
以上。
