LeeCode-198-打家劫舍思路+代码
思路+代码解析
状态转移方程
1、如果只有一家的话，就只能抢这一家，即最优解。
2、如果只有两家的话，最优解为这两家钱最多的一家
3、如果有多于两家的话，关键点为第(n-1)家。如果抢了第(n-1)家，说明在前(n-1)家里已经求得最优解。如果没抢第(n-1)家，说明在前(n-1)家里，小偷在前(n-2)家已经求得最优解，所以小偷也一定会去第n家。那么在n家里最优解为f(n-2)+M(n)。所以在n家里，最优解为f(n-1)和f(n-2)+M(n)中最大值。
递归算法
// 递归
int djjs_dg(vector<int> v)
{
//v代表初始
int len = v.size();
// 只有一家超市，只能抢这家
if (len == 1)
{
return v.at(0);
}
//有两家超市，抢钱多的那家
else if (len == 2)
{
return max(v.at(0), v.at(1));
}
//有n家超市（n>2）
//是否抢n-1的那家，不抢就是前n-2个+第n个
//抢n-1那家就是前n-1家
else
{
vector<int> v1;
vector<int> v2;
//切片
v1.assign(v.begin(), v.end() - 1);
v2.assign(v.begin(), v.end() - 2);
return max(djjs_dg(v1), djjs_dg(v2) + v.at(len - 1));
}
}
DP算法+输出抢的房屋号
vector<int> dp_v; //初始
vector<int> IND; //抢的房屋号
vector<int> DP; //保存dp数组的结果
int djjs_dp(vector<int> v)
{
int len = v.size();
if (len == 1)
{
IND.push_back(0);
return v[0];
}
else if (len == 2)
{
if (v[0] > v[1])
{
IND.push_back(0);
}
else
{
IND.push_back(1);
}
return max(v[0], v[1]);
}
else
{
dp_v.push_back(v[0]); //保存f(i-2)
dp_v.push_back(max(v[0], v[1])); //保存f(i-1)
for (int i = 2; i < len; i++)
{
dp_v.push_back(max(dp_v[i - 1], dp_v[i - 2] + v[i]));
//状态压缩，减小空间复杂度！！！
//只需要保存f(n-1)和f(n-2)两个结果
//dp_v[0] = dp_v[1];
//dp_v[1] = dp_v[i];
}
DP = dp_v;
cout << "DP数组为：" << endl;
for (vector<int>::iterator it = DP.begin(); it != DP.end(); it++)
{
cout << *it << " ";
}
cout << endl;
//dp_v第一次出现最大值的位置对应v的位置是最后一个抢的地方
auto maxPosition = max_element(dp_v.begin(), dp_v.end());
int po = maxPosition - dp_v.begin();
//cout << "1:" << po+1 << endl;
IND.push_back(po);
//如果在这个位置dp_v[po]==v[po]，说明没有抢其他房子
//if (dp_v[po] == v[po]) 不用管
//如果如果在这个位置dp_v[po]>v[po]，说明有抢其他房子
while (dp_v[po] > v[po])
{
//最大值减去在这个位置v的金额，是剩下前面房间的总和
//总和就是dp_v里的某个值
//在dp_v里寻找这个值的位置，对应在v里的位置就是抢的倒数第二个房子
int m = dp_v[po] - v[po];
//cout << "2:" << m << endl;
//返回it迭代器
vector<int>::iterator it = find(dp_v.begin(), dp_v.end(), m);
//cout << "3:" << it - dp_v.begin()+1 << endl;
//返回位置
po = it - dp_v.begin();
IND.push_back(po);
}
return dp_v[len - 1];
}
}
main
void main(){
vector<int> v;
//测试
v.push_back(2);
v.push_back(11);
v.push_back(8);
v.push_back(6);
v.push_back(10);
v.push_back(2);
v.push_back(6);
v.push_back(7);
v.push_back(8);
v.push_back(2);
cout << "初始位置的各金额为：" << endl;
for (vector<int>::iterator it = v.begin(); it != v.end(); it++)
{
cout << *it << " ";
}
cout << endl;
//cout << "递归最优解为：" << djjs_dg(v) << endl;
cout << "DP最优解为：" << djjs_dp(v) << endl;
reverse(IND.begin(), IND.end());
cout << "抢了超市的位置是：" << endl;
for (vector<int>::iterator it = IND.begin(); it != IND.end(); it++)
{
cout << *it + 1 << " ";
}
cout << endl;
}