——永不屈服
一切的开始——数字三角形
在《算法竞赛入门经典》这本书中，数字三角形出现于动态规划初步一章的开头，它也是我入门动态规划的开始。由于它对于我来说也太过简单，所以我只是一笔带过，不作过多停留。
有一个由非负整数组成的三角形，第一行只有一个数，除了最下行之外每个数的左下方和右下方各有一个数，从第一行的数开始，每次可以往左下或右下走一格，直到走到最下行，把沿途经过的数全部加起来。如何走才能使得这个和尽量大？
在求解之前，我们先看看《算法竞赛进阶指南》中如何介绍动态规划的
动态规划算法把原问题视作若干个重叠子问题的逐层递进，每个子问题的求解过程都构成一个“阶段”。
为了保证这些计算能够按顺序、不重复地进行，动态规划要求已经求解的子问题不受后续阶段的影响。这个条件也被叫做“无后效性”。
下一阶段的最优解应该能够由前面各阶段子问题的最优解导出。这个条件被称为“最优子结构性质”
“状态”“阶段”和“决策”是构成动态规划算法的三要素，而“子问题重叠性”“无效性”和“最优子结构性质”是问题能用动态规划求解的三个基本条件。
一般而言，动态规划的思想往往是由记忆化搜索的思考过程中转化而来的，不过在此我直接告诉你 ：
- 每一层的结果，都由上一层推导而出，求解一层的结果即是一个阶段
- 每一层的结果都不会影响之前已经求出的子问题的结果，即无后效性
- 由上一层的最大值能推出这一层的最大值，即最优子结构性质
由子问题重叠性可得，我们要求最终的结果，就可以将问题转化为求上一层的结果，如此反复，最终发现可以由上层向下递推求出答案。详细地说，以[latex]F[i,j][/latex]（i表示行，j表示列）表示该点的子问题结果，显然它的值只受它左上和右上两个点影响，无论是哪边，我们只需取其最优解即可。由此得到方程[latex]F[i,j]=max(F[i-1,j],F[i,j-1])+1)[/latex]，
DP水题的象征——0/1背包
有一个带重量上限m的背包，和n个物品。每个物品有价值vi和重量wi。求如何放物品，使得背包中的价值和最大？
对于每个物品，有两种选择：放入背包（1）或是不放入背包（0）。假设我们不知道这道题该用DP，首先想到的算法应该是搜索，从全0到全1每种情况遍历一遍，找价值和最大的解；还有贪心，遍历所有物品，先将价值大的物品尽量多地放入背包，再补入重量小的物品。结果发现搜索TLE，贪心又并不能证明其正确性。只能DP。
然后我们检查DP的三要素，对于我们要求的问题：n个物品价值和最大。它有子问题：n-1个物品价值和最大-> n-2个物品价值和最大->n-3个物品价值和最大->……->1个物品价值和最大。 子问题是否重复？对于[latex]k\in [2,n][/latex]，我们都是在已知k-1个物品价值和最大的基础上来推出k个物品价值和最大的。而且你可以发现，第n个问题的解并不会影响第n-1个问题的解。用代码来说，以[latex]dp[i][j][/latex]表示的答案数组中，i状态表示前i个物品的结果，j状态表示当前背包已装容量（否则就成了贪心）。显然得到初状态：dp数组全为0，从[latex]dp[1][m][/latex]开始。当状态进行转移时，实质上是考虑物品放或不放对结果的影响：[latex]dp[i][j]=max(dp[i-1][j-w[i]]+v[i],dp[i-1][j])[/latex]
我们把DP数组写成一个m行n列的矩阵，则我们循环的顺序显然是从上往下（从左往右或从右往左无差距）。假如我们有一个大小为10的背包，第一个物品有价值7，重量5，显然得到第一行结果：
0 0 0 0 7 7 7 7 7 7
第二个物品有价值5，重量6，得到第二行结果：
0 0 0 0 7 7 7 7 7 7
这是显然的，因为从价值和重量来看第二个物品都不如第一个物品，再看第三个物品，价值5，重量4，得到第三行结果：
0 0 0 5 7 7 7 7 12 12
在j=4的时候能放入第三个物品，则放入第三个物品的价值显然超过原来0的价值，而在j=9和10的时候能放入第三个和第一个物品，所以价值和为12。
__END__
