一动态规划
是一种在数学、计算机科学和经济学中使用的，通过把原问题分解为相对简单的子问题的方式求解复杂问题的方法。 动态规划算法是通过拆分问题，定义问题状态和状态之间的关系，使得问题能够以递推（或者说分治）的方式去解决。
1.1什么是动态规划
动态规划（Dynamic Programming）对于子问题重叠的情况特别有效，因为它将子问题的解保存在表格中，当需要某个子问题的解时，直接取值即可，从而避免重复计算！
动态规划是一种灵活的方法，不存在一种万能的动态规划算法可以解决各类最优化问题（每种算法都有它的缺陷）。所以除了要对基本概念和方法正确理解外，必须具体问题具体分析处理，用灵活的方法建立数学模型，用创造性的技巧去求解。
1.2基本策略
基本思想与分治法类似，也是将待求解的问题分解为若干个子问题（阶段），按顺序求解子阶段，前一子问题的解，为后一子问题的求解提供了有用的信息。在求解任一子问题时，列出各种可能的局部解，通过决策保留那些有可能达到最优的局部解，丢弃其他局部解。依次解决各子问题，最后一个子问题就是初始问题的解。
动态规划中的子问题往往不是相互独立的（即子问题重叠）。在求解的过程中，许多子问题的解被反复地使用。为了避免重复计算，动态规划算法采用了填表来保存子问题解的方法。
1.3适用问题
那么什么样的问题适合用动态规划的方法来解决呢？
适合用动态规划来解决的问题，都具有下面三个特点：最优化原理、无后效性、有重叠子问题。
（1）最优化原理：如果问题的最优解所包含的子问题的解也是最优的，就称该问题具有最优子结构，即满足最优化原理。
（2）无后效性：即某阶段状态一旦确定，就不受这个状态以后决策的影响。也就是说，某状态以后的过程不会影响以前的状态，只与当前状态有关。
（3）有重叠子问题：即子问题之间是不独立的，一个子问题在下一阶段决策中可能被多次使用到。（该性质并不是动态规划适用的必要条件，但是如果没有这条性质，动态规划算法同其他算法相比就不具备优势。
1.4这类问题的求解步骤通常如下：
初始状态→│决策1│→│决策2│→…→│决策n│→结束状态
（1）划分：按照问题的特征，把问题分为若干阶段。注意：划分后的阶段一定是有序的或者可排序的
（2）确定状态和状态变量：将问题发展到各个阶段时所处的各种不同的客观情况表现出来。状态的选择要满足无后续性
（3）确定决策并写出状态转移方程：状态转移就是根据上一阶段的决策和状态来导出本阶段的状态。根据相邻两个阶段状态之间的联系来确定决策方法和状态转移方程
（4）边界条件：状态转移方程是一个递推式，因此需要找到递推终止的条件
1、5算法实现
动态规划三要素：
（1）问题的阶段
（2）每个阶段的状态
（3）相邻两个阶段之间的递推关系
整个求解过程可以用一张最优决策表来描述，最优决策表是一张二维表（行：决策阶段，列：问题的状态）表格需要填写的数据一般对应此问题的在某个阶段某个状态下的最优值（如最短路径，最长公共子序列，最大价值等），填表的过程就是根据递推关系，最后根据整个表格的数据通过简单的取舍或者运算求得问题的最优解。
例如：f(n,m)=max{f(n-1,m), f(n-1,m-w[n])+P(n,m)}
二：事例
2.1背包问题
问题描述：假设我们有n种类型的物品，分别编号为1, 2...n。其中编号为i的物品价值为vi，它的重量为wi。为了简化问题，假定价值和重量都是整数值。现在，假设我们有一个背包，它能够承载的重量是Cap。现在，我们希望往包里装这些物品，使得包里装的物品价值最大化，那么我们该如何来选择装的东西呢？注意：每种物品只有一件，可以选择放或者不放。初始化数据为：n=5，w={2,2,6,5,4}，v={6,3,5,4,6}，Cap=10
解法如下：
A)描述最优解的结构
设子问题：f[i][v]表示允许前i件物品放入容量为v的背包时可以获得的最大价值。注：这里的i从0到5，v从0到10
为了能够得到已经计算过的，更小规模的子问题，我们可以根据当前限重来只考虑第i件物品放或者不放，那么就可以转化为涉及前i-1件物品的问题，
即：
情况1、如果第i件物品不能放（即这个物品的重量直接大于了当前限重v），则问题转化为“前i-1件物品放入容量为v的背包中”，即f[i-1][v]；
情况2、如果放第i件物品是可以放也可以不放，则问题转化为：
1）、如果选择不放第i件物品，则问题转化为“前i-1件物品放入容量为v的背包中”，即变大时f[i-1][v]；
2）、如果选择放第i件物品，则问题转化为“前i-1件物品放入剩下的容量为v-w[i]的背包中”，此时能获得的最大价值就是f [i-1][v-w[i]]再加上通过放入第i件物品获得的价值v[i]。
则情况2下，f[i][v]的值就是1），2）中最大的那个值。
最优子结构描述如下：当子问题f[i][v]是最优时，其子问题f[i-1][v]和f[i-1][v-w[i]]（中的较大者）显然同样也必须是最优的值，不然在情况1或者情况2下总会矛盾。
B) 递归定义最优解的值
根据上面的分析，显然子问题
f[i][v]=f[i-1][v]，这时是情况1
f[i][v]=max{f[i-1][v], f[i-1][v-w[i]]+v[i] }，这时是情况2。
class Solution(object):
def backPack(self, v, weight, value):
'''
:paramv: 背包的总容量
:paramweight: 每个物品的容量数组表示
:paramvalue: 每个物品的价值
:return: 放回最大总价值
'''
N =len(value)
# 初始化[N+1][V+1]为0， f[i][j]表示前i件物品恰放入一个容量为j的背包可以获得的最大价值
f = [[0 for i in range(v+1)]for j in range(N+1)]
for iin range(1, N+1):
for jin range(1, v+1):
if j < weight[i-1]:#总容量j 小于物品i的容量时，直接不考虑物品i
f[i][j] = f[i-1][j]
else:
# 注意由于weight， value数组的下标从0开始，第i个物品的容量为weight[i-1],价值为value[i-1]
f[i][j] =max(f[i-1][j], f[i-1][j-weight[i-1]]+value[i-1])# 状态方程
return f[N][v]
if __name__ =='__main__':
v, weight, value =10, [2, 3, 5, 7], [1, 5, 2, 4]
print(Solution().backPack(v, weight, value))
参考连接：https://blog.csdn.net/SweetSeven_/article/details/95466195
