随便扯一个61A的题目好了（其实是我太懒不想找题...）
不知道你还记得不记得61A的某个MT的leaps那道题。
有一排N个宝藏，从左到右每个宝藏价值分别为vi。地精可以拿走其中一些宝藏，但是不能取相邻的宝藏。求最大价值和。
例如有6个宝藏，价值分别为2 5 2 1 4 1。我可以取2 2 4、5 1 1、5 4等等，但是不能取2 5 2，因为2和5是相邻的。
令f[i]为前i个宝藏中取走若干个所能获得的最大收益
易知，f[1] = v[1]，f[2] = max(v[1], v[2])（为什么？）
f[i] = max(f[i-1], f[i-2] + v[i])
answer = f[N]
比如上例中，f[1] = 2, f[2] = max(2,5) = 5
f[3] = max(f[2], f[1]+v[3]) = max(5, 2+2) = 5
f[4] = max(5, 5+1) = 6
f[5] = max(6, 5+4) = 9
f[6] = max(9, 6+1) = 9
f[6]表示的是前6个宝藏中取走若干个可以获得的最大收益，而我们总共只有6个宝藏，所以“前6个”就是全部的宝藏。所以f[6]就是上例的答案。
（这题中我有两个类似base case的东西，分别是f[1] = v[1]、f[2] = max(v[1],v[2])。实际上也可以用f[0] = 0、f[1] = v[1]，体会一下。）
这题在61A中的做法是recursion，但是recursion的常数是很大的，而且如果没有记忆化的话复杂度是指数级的。用DP可以达到像记忆化一样的时间复杂度（O(N)），而且相比记忆化，DP的时间空间开销都很小，代码也短。
完整伪代码如下:
for i = 1 to N
read v[i]
f[0] = 0
f[1] = v[1] -- 假如N = 0怎么办？ => 写程序的时候要注意细节。这里为了程序简洁忽略了特殊情况，实际做题的时候是要特判的。
for i = 2 to N
f[i] = max(f[i-1], f[i-2]+v[i])
print f[N]
上面的程序如果翻译成C/C++/Java的话，在大部分电脑上可以瞬间解出N = 10000000的大数据。这就是算法的力量。