记忆化搜索

记忆化搜索是一个剪枝的过程，将搜索速度加快。将讨论的情况数目减少。
下面以数字金字塔为例：
要求：输入一个找到一个从上到下权值最大的路径，并将该权值输出。
'样例数据'：

    4
   1 2
  7 8 1
11 8 1 6

'样例输出'：23
'样例分析'：
如果我们按照贪心策略，从上到下每次寻找左右最大的一个，得到的路径将是：4->2->8->8，权值和为22.
实际上该路线并非权值最大的路径，最大的是4->1->7->11，权值和23.
这里体现的是贪心算法并不适用。贪心算法的条件：无后效性。
而在这里，如果我们到达了第三行的"8",而非"7",我们就不能选择到左下角那个很有诱惑力的"11",这就体现了后效性：当前做出的选择，会对未来产生影响。
所以使用搜索算法，讨论每一种情况。我们使用dp[i][j]代表从最顶端到当前位置（i,j)的最大权值。

第一行：
到dp[1][1]，权值即为(1,1)位置上的数字。
第二行：
dp[2][1]只能从(1,1)到达，所以dp[2][1]=dp[1][1]+num[2][1]；
dp[2][2]，同理。dp[2][2]=dp[1][1]+num[2][2]；
第三行：
dp[3][1]只能从(2,1)到达，dp[3][1]=dp[2][1]+num[3][1]；
dp[3][2]可以从(2,1)或(2,2)到达，那么当然要挑从权值大的那个过来，dp[3][2]=max(dp[2][1],dp[2][2])+num[3][2]；
dp[3][3]只能从(2,2)到达，dp[3][3]=dp[2][2]+num[3][3]；
第四行
dp[4][1]只能从(3,1)到达，dp[4][1]=dp[3][1]+num[4][1]；
dp[4][2]可以从(3,1)或(3,2)到达，从权值大的地方过来。dp[4][2]=max(dp[3][1],dp[3][2])+num[4][2]；
dp[4][3]可以从(3,2)或(3,3)到达，从权值大的地方过来。dp[4][3]=max(dp[3][2],dp[3][3])+num[4][3]；
dp[4][4]只能从(3,3)到达，dp[4][4]=dp[3][3]+num[4][4]；
最后，遍历一遍最后一排，找到dp值最大的，输出就行了。

动态规划

01背包问题

01背包问题：共有n个不同种的物品，每种物品只有一件。这些物品具有两个属性：w（重量）和v（价值），且物品不可分割。你的背包最多能装M质量的物品，求最优解

01背包问题和之前的问题的区别：并fe