LeetCode-打家劫舍

LeetCode-打家劫舍,第1张

打家劫舍

  • 动态规划问题
  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;
}

欢迎分享,转载请注明来源:内存溢出

原文地址: http://outofmemory.cn/langs/568371.html

(0)
打赏 微信扫一扫 微信扫一扫 支付宝扫一扫 支付宝扫一扫
上一篇 2022-04-09
下一篇 2022-04-09

发表评论

登录后才能评论

评论列表(0条)

保存