LeetCode-打家劫舍

打家劫舍

• 动态规划问题

1. 观察。
   

   
   

   我们设置dp数组，下标表示打劫房子序号，数值表示路过当前房子可打劫最大金额(因为相邻房子无法打劫，只能路过了)。
   

   
   

2. 确定状态方程。
   

   
   

   假设我们想打劫第n个房子，那么我们应该考虑到，第n-1个房则无法打劫，也就是说，我们当前总额只能从前n-2间房子打捞金额加上当前想要打劫房子的金额，但万一我们不想打劫第n间房子呢？这种情况出现在，假设我们通过例外一条打劫途径打劫了第n-1个房子，而且他的金额比打劫第n个房子金额还要多，那我们只能路过第n个房子了。
   

   
   

   这样我们就确定了状态方程了。
   

   
   

   dp[i]=max{dp[i-1],nums[i]+dp[i-2]}

3. 确定边界条件。
   

   
   

   边界条件一般可通过状态方程得知，很明显i-2>=0，i-1>=0。
   

   
   

   由于i>=2，所以我们初始dp[0]，dp[1]即可。
   

   
   

   我们可以选择打劫第0个房子，或者打劫第1个房子，不论如何，路过到第1间房子，他的值总是第0和第1间房子中最大金额。
   

   
   

   值得注意的是，当只有一间房子时，我们直接返回这个房子的金额。
   

   
   

   确定了这一边界条件，利用状态方程就可以完成打劫啦。
   

   
   

4. 返回dp[numsSize-1]就行了。
   

   
   

int rob(int* nums, int numsSize){
    if(numsSize==1)
    return nums[0];
int dp[numsSize];
dp[0]=nums[0];
dp[1]=fmax(nums[0],nums[1]);
for(int i=2;i<numsSize;i++)
{
    dp[i]=fmax(dp[i-1],dp[i-2]+nums[i]);
}
return dp[numsSize-1];
}

当然，了解到了具体过程，我们可以用变量代替数组从而减少空间复杂度

int rob(int* nums, int numsSize){
    if(numsSize==1)
    return nums[0];
int a=0,b=0,c=0;
a=nums[0];
b=fmax(nums[0],nums[1]);
for(int i=2;i<numsSize;i++)
{
    c=fmax(b,a+nums[i]);
    a=b;
    b=c;
}
return c==0?(a>b?a:b):c;
}