说明：算法源自教材。本文相当于对教材做的一个笔记

首先：动态规划能够成立的前提是：原问题具备重叠子问题和最优子结构的性质

重叠子问题：存在子问题会被重复计算多次。以经典的斐波拉契数列F(n)=F(n - 1)+F(n - 2)为例：求解f5原问题时，子问题f2被重复求解了3次。

 最优子结构：子问题相互独立且子问题的最优解可以推出原问题的最优解（局部最优可以推出全局最优：f1，f2的解可以推出f3的解，且f1不会影响f2）。举一个生活中的例子，引用自labuladong动态规划详解

比如说，假设你考试，每门科目的成绩都是互相独立的。你的原问题是考出最高的总成绩，那么你的子问题就是要把语文考到最高，数学考到最高…… 为了每门课考到最高，你要把每门课相应的选择题分数拿到最高，填空题分数拿到最高…… 当然，最终就是你每门课都是满分，这就是最高的总成绩。

得到了正确的结果：最高的总成绩就是总分。因为这个过程符合最优子结构，“每门科目考到最高”这些子问题是互相独立，互不干扰的。

但是，如果加一个条件：你的语文成绩和数学成绩会互相制约，数学分数高，语文分数就会降低，反之亦然。这样的话，显然你能考到的最高总成绩就达不到总分了，按刚才那个思路就会得到错误的结果。因为子问题并不独立，语文数学成绩无法同时最优，所以最优子结构被破坏。

动态规划算法：     动态规划就是一个填表的过程。该表记录了已解决的子问题的答案。求解下一个子问题时会用到上一个子问题的答案。{比如01背包问题：假如有1个背包，背包容量是10，有5个物品，编号为1，2，3，4，5，他们都有各自的重量和价格。要求在不超过背包容量的情况下，使背包装载物品的价值最大。现将问题拆分为五个子问题。 1.背容=10，从1号物品中找出该问题的解 2.背容=10，从1号，2号物品中找出该问题的解 3.背容=10，从1号，2号，3号物品中找出该问题的解 4.背容=10，从1号，2号，3号，4号物品中找出该问题的解 5.背容=10，从1号，2号，3号，4号，5号物品中找出该问题的解 }思路：    我们可以将1，2，3，4，5子问题的答案都存入一张表中。因为求解2子问题，需要用到1子问题的答案(2的每一步方案要与1的每一步方案比较，如何2的该步方案优于1所对应的方案。则将2的这步方案标为可行。如果不优于1的，或者不满足问题的约束条件，则舍弃该方案。继续沿用该步所对应的1的方案作为该步的方案)。求解3子问题，需要用到2子问题的答案，一直递推到求解5子问题，需要用到4子问题的答案。而5子问题就是原问题。5子问题的答案就是最终原问题的解。  

解法：

       以01背包问题为例，作讲解。给出问题参数：

运行的最终结果是张二维表：（f[i][j],i就是n，j就是c）

填表相关说明：

1.程序是一行一行的进行填表的。f[0][0,1,2,3,4.....]......f[5][0,1,2,3,4....]  (程序初始化的过程就是将第0行的所有数填为0，这是符合现实情况的。它表明当前背包没有装物品，当前背包的价值是0)

2.拿f[3][8]=11来说明填表的过程。f[3]表明i=3(当前子问题有3个物品可选，分别是1，2，3号物品)，f[3][*]的值就是第3个子问题的解。我要选的3号物品的重量是6，它的价值是5，所以我会找到它的前6列的上一行所对应的背包的价值（f[2][2]）+5（当前要选的3号物品的价值）=11,值为11>f[2][8]=9，代表我选了1,3的方案要优于选1，2的这种方案，所以我将11填入到表格【如果f[2][2]+5>>>背价=？，背包价格是多少，{1，3}>>>>背价=？,{1，2,3}>>>>背价=？而{1,2}>>背包价格在2子问题中已给出，因此我们可以在3子问题中直接用。为何不考虑{2，3}呢？就是拿2号和3号组队放入背包？因为在2子问题中已经记载了：【如果要单选一个背包的话，选择1号获得的价值要比2号获得的价值大----我们追溯到f[2][2]=6是整么来的，背包容量是2的时候，[1,2]号物品只能有一个放入背包，放入1，背包的价值是6，f[1][2]=6的计算是在1子问题中已经求解出来的，2子问题可以直接用该值，而不用再重复计算。放入2号，背值是3，3