网站建设与推广完美结合,郑州微信网站,win7建网站教程,网站素材下载目录1、题目2、求解思路3、代码1、题目
你是一个专业的小偷#xff0c;计划偷窃沿街的房屋。每间房内都藏有一定的现金#xff0c;影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统#xff0c;如果两间相邻的房屋在同一晚上被小偷闯入#xff0c;系统会自动… 目录1、题目2、求解思路3、代码 1、题目
你是一个专业的小偷计划偷窃沿街的房屋。每间房内都藏有一定的现金影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统如果两间相邻的房屋在同一晚上被小偷闯入系统会自动报警。
给定一个代表每个房屋存放金额的非负整数数组计算你 不触动警报装置的情况下 一夜之内能够偷窃到的最高金额。 2、求解思路
1、确定总目标从0~nums.size()-1个房子中能偷到的最大金额 2、确定子问题从 0~k 个房子中能偷到的最大金额,knums.size()-1就是原问题。原问题要能由子问题表示。 3、分析状态方程一个子问题的解要能通过其他子问题的解求出。 对于每个房屋我们有两种选择偷或者不偷 如果选择偷第i个房屋那么第i-1个房屋肯定不能偷问题转化为前i-2个房屋中最大价值最后再加上第i个房屋的价值构成第前i个房屋中最大价值。 如果选择不偷第i个房屋那么第i-1个房屋肯定能偷问题转化为前i-1个房屋中最大价值构成第前i个房屋中最大价值。 所以状态方程确定
dp[i]max(dp[i-1],dp[i-2]nums[i]);4、边界条件 当只有一个房屋时一定偷这个房屋。 当只有两个房屋时选择偷两个中价值较大的房屋。 5、空间优化 对于小偷问题我们发现最后一步计算 dp[i]的时候实际上只用到了dp[i-1] 和 dp[i-2] 的结果。 那么我们可以只用两个变量保存两个子问题的结果就可以依次计算出所有的子问题。
int ScrollingArray[2]0;
//循环开始时ScrollingArray[1]表示 dp[i-1]ScrollingArray[0]表示 dp[i-2]
for(int i2;isize;i)
{//dp[i] max{ dp[i-1], dp[i-2] nums[i] }int temp max(ScrollingArray[1],ScrollingArray[0]nums[i]);//dp[i-2] dp[i-1];ScrollingArray[0]ScrollingArray[1];//dp[i-1]dp[i]ScrollingArray[1] temp;
}3、代码
1、没有滚动数组优化
class Solution {
public:int rob(vectorint nums) {int size nums.size();if(size0) return 0;else if(size 1) return nums[0];else if(size 2) return max(nums[1],nums[0]);vectorint dp(size,0);dp[0]nums[0];dp[1]max(nums[1],nums[0]);//对于每一个房间有不偷和偷两种结果我们取价值最大的。for(int i2;isize;i) dp[i]max(dp[i-1],dp[i-2]nums[i]);return dp[size-1];}
};2、加了滚动数组优化;
class Solution {
public:int rob(vectorint nums) {int size nums.size();if(size0) return 0;else if(size 1) return nums[0];else if(size 2) return max(nums[1],nums[0]);int ScrollingArray[2]{0};ScrollingArray[0]nums[0];ScrollingArray[1]max(nums[1],nums[0]);//循环开始时ScrollingArray[1]表示 dp[i-1]ScrollingArray[0]表示 dp[i-2]for(int i2;isize;i) {//dp[i] max{ dp[i-1], dp[i-2] nums[i] }int temp max(ScrollingArray[1],ScrollingArray[0]nums[i]);//dp[i-2] dp[i-1];ScrollingArray[0]ScrollingArray[1];//dp[i-1]dp[i]ScrollingArray[1] temp;}return ScrollingArray[1];}
};
