1、动态规划与分治法的相似点：都是将待求问题分解成若干个子问题，先求解出这些子问题，然后从子问题的解得到原问题的解
不同点：适合用动态规划求解的问题，经分解得到的子问题一般不是互相独立的。
2、动态规划算法通常用于求解具有某种最优性质的问题。在这类问题中可能有许多可行解，每一个解都对应一个值，希望找到具有最优值的解。
3、动态规划算法的有效性依赖于最优子结构 和 子问题重叠
最优子结构 指的是问题的最优解 包含了 其子问题的最优解，使得程序能以自底向上的方式递推地从子问题的最优解逐步 构造出 整个问题的最优解
子问题重叠 指的是对某些子问题重复求解多次，动态规划能存储这些解。
4、解决动态规划的问题的手段：
第一：递归:先自上到底 再 自底到上 优势：正着由大规模问题推向小规模问题，容易想 劣势：但是效率低。
第二：迭代递推： 直接自底向上 优势 效率高 劣势：不好想
5、写动态规划算法，最重要的是要找到动态规划递推式
0-1背包问题，如果有n个物品，它们的重量分别为w1，w2......wn，价值分别为v1，v2....vn，现有一个负重为k的背包，要求选择物品装入背包，
使背包中物体总价值最大。
1、背包的状态转换方程 f[i,j] = Max{ f[i-1,j-Wi]+Pi( j >= Wi ), f[i-1,j] }//前者表示放入第i件物品(如果超出重量价值为0) 后者表示不放入第i件物品，在假 设前面已经是最优解的情况下，放不放第i件不影响前面作出的决策
/*** c[i][w]表示背包容量为w时，i个物品导致的最优解的总价值，大小为(n+1)*(w+1) v[i]表示第i个物品的价值，大小为n w[i]表示第i个物品的重量，大小为n ***/ void DP(int n, int W, int c[][18], int *v, int *wei) { memset(*c, 0, (W+1)*sizeof(int)); for (int i = 1; i <= n; i++) { c[i][0] = 0; for (int w = 1; w <= W; w++) i个物体时，在不同w下的最优解{ if (wei[i-1] > w) //此处比较是关键 { c[i][w] = c[i-1][w]; } else { int temp = c[i-1][w-wei[i-1]] + v[i-1]; //注意wei和v数组中的第i个应该为wei[i-1]和v[i-1] if (c[i-1][w] > temp) { c[i][w] = c[i-1][w]; } else c[i][w] = temp; } } } } void findPath(int c[][18], int *x, int *wei, int n, int W) { int w = W; for (int i = n; i >= 2; i--) { if (c[i][w] == c[i-1][w]) { x[i-1] = 0; } else { x[i-1] = 1; w = w - wei[i-1]; } } if (c[1][w] == 0) x[0] = 0; else x[0] = 1; }
f[i,j]表示在前i件物品中选择若干件放在承重为 j 的背包中，可以取得的最大价值。
Pi表示第i件物品的价值。
决策：为了背包中物品总价值最大化，第 i件物品应该放入背包中吗 ？