一道简单DP题

一.算法题干

二.基本思路

首先，一看就应该知道这是一道DP题。原因在于其当前结果都依赖于前面计算得到的子结果。区分分治和DP的关键条件就在于算法运行中间阶段的计算结果是否依赖于其子问题的结果，若依赖则为DP，否则为分治。
DP题的关键在于找出状态转移方程和初始条件（或者称为边界值）。找出状态转移方程的关键又在于找对一个状态函数。根据我目前的经验，这种状态一般都是一个局部最优结果，如本题就可以设f(k)为前k-1项结果的最大值。
下一步，我习惯先找状态转移方程，再根据状态转移方程找出边界条件的值。很容易想到，状态转移方程为f(k)=max(f(k-2)+A_k,f(k-1))。这其实意味着第k个元素是否取得，max函数中前者代表取，后者代表不取。这里的技巧感觉只能慢慢体会，别人讲恐怕也只能讲到这个地步了。
进而，可以看出，在k=1时，k-2为-1，k-1为0。这里不从k=2开始遍历，是因为未必第1（从0开始）个元素取还是不取（这取决于A₀和A₁的相对大小），这里也算是一个坑吧。
f(-1)和f(0)的取值显而易见。特别是f(-1)，这种下标不在正常范围里的，一般都是特殊值，如0、1，这取决于题目具体要求解的是什么。
确定了状态转移方程和边界条件后，就可以很容易地得到以下代码。

int rob(vector<int>& v) {
	int l=v.size();
	if(!l) return 0;
	vector<int> t(l+1);
	t[0] = 0;
	t[1] = v[0];
	for(int i=2;i<l+1;++i)
	{
		t[i] = max(t[i-2]+v[i-1],t[i-1]);
	}
	return t[l];
}

另外，最开始对特殊情况的判断也是一个坑，只要题目没有明确说明“不为空”“>0”之类的字眼，在代码开头加入一些特殊情况的判断还是非常有必要的，只不过我经常会忘记……
vector五种构造函数参见【STL】vector的五种构造函数。STL的使用还是要非常熟练才行。

三.改进方案

先直接看代码。

int rob(vector<int>& v) {
	int cur=0,pre=0;
	for(auto i:v)
	{
		int tmp = cur;
		cur = max(cur,pre+i);
		pre = tmp;
	}
	return cur;
}

这里最奇妙的技巧就是只使用了两个变量，让原本为O(n)的空间复杂度降为了O(1)。这里充分利用了计算当中只依赖于前面两种情况的特性。这里可以推而广之，如果状态转移方程中只涉及前面两种局部结果，那么都可以采用这种减少空间复杂度的方法。

四.题目来源

198. 打家劫舍