打家劫舍 II问题的动态规划解决方案及C++代码实现

这篇具有很好参考价值的文章主要介绍了打家劫舍 II问题的动态规划解决方案及C++代码实现。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

个人主页:元清加油_【C++】,【C语言】,【数据结构与算法】-CSDN博客

个人专栏

力扣递归算法题

【C++】    

数据结构与算法


打家劫舍 II

题目链接:打家劫舍 II

题目

你是一个专业的小偷,计划偷窃沿街的房屋,每间房内都藏有一定的现金。这个地方所有的房屋都 围成一圈 ,这意味着第一个房屋和最后一个房屋是紧挨着的。同时,相邻的房屋装有相互连通的防盗系统,如果两间相邻的房屋在同一晚上被小偷闯入,系统会自动报警 。

给定一个代表每个房屋存放金额的非负整数数组,计算你 在不触动警报装置的情况下 ,今晚能够偷窃到的最高金额。

示例 1:

输入:nums = [2,3,2]输出:3解释:你不能先偷窃 1 号房屋(金额 = 2),然后偷窃 3 号房屋(金额 = 2), 因为他们是相邻的。

示例 2:

输入:nums = [1,2,3,1]输出:4解释:你可以先偷窃 1 号房屋(金额 = 1),然后偷窃 3 号房屋(金额 = 3)。
     偷窃到的最高金额 = 1 + 3 = 4 。

示例 3:

输入:nums = [1,2,3]输出:3

提示:

  • 1 <= nums.length <= 100

  • 0 <= nums[i] <= 1000


解法

算法原理讲解

我们这题使用动态规划,我们做这类题目可以分为以下五个步骤

  1. 状态显示

  2. 状态转移方程

  3. 初始化(防止填表时不越界)

  4. 填表顺序

  5. 返回值

这⼀个问题是⼀个「环形」的模式,也就是⾸尾是相连的。但是我们可以将「环形」问题转化为「两个单排」问题:

  • 偷第⼀个房屋时的最大金额 x ,此时不能偷最后⼀个房⼦,因此就是偷 [0, n - 2] 区间的房子;

  • 不偷第⼀个房屋时的最大金额 y ,此时可以偷最后⼀个房⼦,因此就是偷 [1, n - 1] 间的房子;

两种情况下的「最⼤值」,就是最终的结果。因此,问题就转化成求「两次单排结果的最⼤值」。

  • 状态显示

dp1[i]表示:偷到 i 位置,偷 nums[i],此时最大的金额。

dp2[i]表示:偷到 i 位置,不偷 nums[i],此时最大的金额。

  • 状态转移方程

dp1[i] = dp2[i-1] + nums[i]

dp2[i] = max(dp1[i-1], dp2[i-1])

  • 初始化(防止填表时不越界)

dp1[left] = nums[left];

  • 填表顺序

根据「状态转移⽅程」得「从左往右,两个表⼀起填」。

  • 返回值

max(dp1[right], dp2[right])


代码实现

  • 时间复杂度:O(n),其中 n 是数组长度。需要对数组遍历两次,计算可以偷窃到的最高总金额。

  • 空间复杂度:O(n)。

class Solution 
{
public:
    int rob(vector<int>& nums)
    {
        int n = nums.size();
        // 两种情况下的最⼤值
        return max(nums[0] + rob1(nums, 2, n - 2), rob1(nums, 1, n - 1));
    }

    int rob1(vector<int>& nums, int left, int right)
    {
        if(left > right) 
        {
            return 0;
        }
        // 1. 创建 dp 表
        // 2. 初始化
        // 3. 填表
        // 4. 返回结果
        int n = nums.size();
        vector<int> dp1(n);
        auto dp2 = dp1;

        dp1[left] = nums[left]; // 初始化
        for(int i = left + 1; i <= right; i++)
        {
            dp1[i] = dp2[i - 1] + nums[i];
            dp2[i] = max(dp1[i - 1], dp2[i - 1]);
        }
        return max(dp1[right], dp2[right]);
    }
};

C++,C++动态规划,C++环形问题,力扣动态规划算法题文章来源地址https://www.toymoban.com/news/detail-813021.html

到了这里,关于打家劫舍 II问题的动态规划解决方案及C++代码实现的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • Java 动态规划 Leetcode 213. 打家劫舍 II

    代码展示:         该题其实是Java 动态规划 面试题 17.16. 按摩师的变种,增加了一个首尾是相邻的条件,而我们解决该题也要用到链接的这道题的思想,可以先去看一下上面这篇博客 此题可以采用动态规划的方法进行解决,根据解决动态规划题目的5大步骤进行逐步分析

    2024年02月13日
    浏览(40)
  • 【动态规划】简单多状态dp问题(1)打家劫舍问题

    打家劫舍问题 传送门:面试题 17.16. 按摩师 题目: 1.1 题目解析 越难的dp问题,看示例只能起到了解题目的效果,一般推不出啥普遍的规律,所以接下来就是我们的算法原理,通过动归的思想去理解,才会豁然开朗! 1.2 算法原理 1.2.1 状态表示 我们需要通过经验 + 题目要求去

    2024年02月12日
    浏览(43)
  • 【四】【C语言\动态规划】地下城游戏、按摩师、打家劫舍 II,三道题目深度解析

    动态规划就像是解决问题的一种策略,它可以帮助我们更高效地找到问题的解决方案。这个策略的核心思想就是将问题分解为一系列的小问题,并将每个小问题的解保存起来。这样,当我们需要解决原始问题的时候,我们就可以直接利用已经计算好的小问题的解,而不需要重

    2024年02月04日
    浏览(46)
  • 力扣爆刷第77天--动态规划一网打尽打家劫舍问题

    力扣爆刷第77天–动态规划一网打尽打家劫舍问题 一、198.打家劫舍 题目链接:https://leetcode.cn/problems/house-robber/ 思路:小偷不能连续两家偷,由此可以定义dp[i]表示,小偷经过[0,i]所能获取到的最大金额,那么我们可以得到递推公式: dp[i] = Math.max(dp[i-1], dp[i-2]+nums[i]); 即如果偷

    2024年02月22日
    浏览(48)
  • 动态规划_打家劫舍(Ⅰ~Ⅲ)

    打家劫舍系列 返回最大金额 不能同时取相邻两个数 数组数据全部非负 ①dp数组含义 dp[i]表示前i个数中按规则取出的最大总和 ②递推公式 dp[i]=max(dp[i-1],dp[i-2]+nums[i]) 当前最优可以从两个状态推出(前提是前面已经为最优解): 1° 前一个数未取:则当前数取了,则总和最大

    2024年02月03日
    浏览(41)
  • 力扣198. 打家劫舍(java 动态规划)

    Problem: 198. 打家劫舍 1.构建多阶段决策模型:n个房屋对应n个阶段,每一个阶段决定一个房间是偷还是不偷,两种决策:偷、不偷 2.定义状态:不能记录每个阶段决策完之后,小偷可偷的最大金额,需要记录不同决策对应的最大金额,也就是:这个房屋偷-对应的最大金额;这

    2024年01月21日
    浏览(55)
  • leetcode-打家劫舍专题系列(动态规划)

    你是一个专业的小偷,计划偷窃沿街的房屋。每间房内都藏有一定的现金,影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统,如果两间相邻的房屋在同一晚上被小偷闯入,系统会自动报警。 给定一个代表每个房屋存放金额的非负整数数组,计算你 不触动

    2024年04月14日
    浏览(45)
  • 动态规划-经典dp(打家劫舍,股票等)

    1.1.1 爬楼梯  由于求的是组合数,我们将不同路径相加即可 dp定义: dp[i]为爬到第i阶楼梯的方法数; 转移方程: 初始化:  由于涉及到i-2和i-1,那么我们要从i=2开始遍历,因此要初始化dp[0] = 0,dp[1] = 1(根据定义) 遍历顺序: 从左往右  完整代码:  1.1.2 使用最小花费爬楼梯

    2024年01月19日
    浏览(38)
  • 【LeetCode热题100】198. 打家劫舍(动态规划)

    你是一个专业的小偷,计划偷窃沿街的房屋。每间房内都藏有一定的现金,影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统, 如果两间相邻的房屋在同一晚上被小偷闯入,系统会自动报警。 给定一个代表每个房屋存放金额的非负整数数组,计算你 不触动

    2024年04月11日
    浏览(47)
  • Day 42 算法记录|动态规划 09 (打家劫舍)

    1.dp[i]:考虑下标i(包括i)以内的房屋,最多可以偷窃的金额为dp[i]。 2.dp[i] = max(dp[i - 2] + nums[i], dp[i - 1]); 3.初始化,dp[0] 和 dp[1],dp[0] 一定是 nums[0],dp[1] = max(nums[0], nums[1]); 3.遍历顺序,dp[i] 是根据dp[i - 2] 和 dp[i - 1] 推导出来的,那么一定是从前到后遍历! 进一步对滚动数组

    2024年02月15日
    浏览(34)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包