LeetCode213. House Robber II——动态规划

这篇具有很好参考价值的文章主要介绍了LeetCode213. House Robber II——动态规划。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

一、题目

You are a professional robber planning to rob houses along a street. Each house has a certain amount of money stashed. All houses at this place are arranged in a circle. That means the first house is the neighbor of the last one. Meanwhile, adjacent houses have a security system connected, and it will automatically contact the police if two adjacent houses were broken into on the same night.

Given an integer array nums representing the amount of money of each house, return the maximum amount of money you can rob tonight without alerting the police.

Example 1:

Input: nums = [2,3,2]
Output: 3
Explanation: You cannot rob house 1 (money = 2) and then rob house 3 (money = 2), because they are adjacent houses.
Example 2:

Input: nums = [1,2,3,1]
Output: 4
Explanation: Rob house 1 (money = 1) and then rob house 3 (money = 3).
Total amount you can rob = 1 + 3 = 4.
Example 3:

Input: nums = [1,2,3]
Output: 3

Constraints:

1 <= nums.length <= 100
0 <= nums[i] <= 1000文章来源地址https://www.toymoban.com/news/detail-828361.html

二、题解

class Solution {
public:
    int rob(vector<int>& nums) {
        int n = nums.size();
        if(n == 1) return nums[0];
        return max(best(nums,1,n-1),nums[0] + best(nums,2,n-2));
    }
    int best(vector<int>& nums,int l,int r){
        if(l > r) return 0;
        if(l == r) return nums[l];
        if(l + 1 == r) return max(nums[l],nums[r]);
        int prepre = nums[l],pre = max(nums[l],nums[l + 1]);
        for(int i = l + 2;i <= r;i++){
            int cur = max(pre,nums[i] + max(prepre,0));
            prepre = pre;
            pre = cur;
        }
        return pre;
    }
};

到了这里,关于LeetCode213. House Robber II——动态规划的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

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

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

相关文章

  • LeetCode算法题解(动态规划)|LeetCoed62. 不同路径、LeetCode63. 不同路径 II

    题目链接:62. 不同路径 题目描述: 一个机器人位于一个  m x n   网格的左上角 (起始点在下图中标记为 “Start” )。 机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角(在下图中标记为 “Finish” )。 问总共有多少条不同的路径? 示例 1: 示例 2:

    2024年02月05日
    浏览(49)
  • 【算法|动态规划No.10】leetcode LCR 089. 打家劫舍 & LCR 090. 打家劫舍 II

    个人主页:兜里有颗棉花糖 欢迎 点赞👍 收藏✨ 留言✉ 加关注💓本文由 兜里有颗棉花糖 原创 收录于专栏【手撕算法系列专栏】【LeetCode】 🍔本专栏旨在提高自己算法能力的同时,记录一下自己的学习过程,希望对大家有所帮助 🍓希望我们一起努力、成长,共同进步。

    2024年01月20日
    浏览(43)
  • leetcode 213. 打家劫舍 II

             本题是 打家劫舍 的进阶版,房屋之间形成一个环了,也就是第一个房屋和最后一个房屋不能一起偷了。那么能偷的情况分为下列三种: 不考虑偷首房间。 不考虑偷尾房间。 不考虑偷首尾房间。         第三种情况包含于第一和第二种情况了,所以分别为第一种

    2024年02月12日
    浏览(31)
  • leetcode63. 不同路径 II(动态规划-java)

    来源:力扣(LeetCode) 链接:https://leetcode.cn/problems/unique-paths-ii 一个机器人位于一个 m x n 网格的左上角 (起始点在下图中标记为 “Start” )。 机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角(在下图中标记为 “Finish”)。 现在考虑网格中有障碍物。

    2024年02月11日
    浏览(47)
  • leetcode动态规划(零钱兑换II、组合总和 Ⅳ)

    给定不同面额的硬币和一个总金额。写出函数来计算可以凑成总金额的硬币组合数。假设每一种面额的硬币有无限个。 示例 1: 输入: amount = 5, coins = [1, 2, 5] 输出: 4 解释: 有四种方式可以凑成总金额: 5=5 5=2+2+1 5=2+1+1+1 5=1+1+1+1+1 示例 2: 输入: amount = 3, coins = [2] 输出: 0 解释: 只用面

    2024年02月01日
    浏览(41)
  • LeetCode264. 丑数 II(相关话题:多重指针动态规划)

    给你一个整数  n  ,请你找出并返回第  n  个  丑数  。 丑数  就是质因子只包含  2 、 3  和  5  的正整数。 示例 1: 示例 2: 提示: 1 = n = 1690 动态规划数组:dp 数组用于存储从第 1 个到第 n 个丑数。dp[0] 初始化为 1,因为第一个丑数定义为 1。 三个指针:p2、p3、p5 分

    2024年01月20日
    浏览(40)
  • (动态规划) 132. 分割回文串 II ——【Leetcode每日一题】

    难度:困难 给你一个字符串 s ,请你将 s 分割成一些子串,使每个子串都是回文。 返回符合要求的 最少分割次数 。 示例 1: 输入:s = “aab” 输出:1 解释:只需一次分割就可将 s 分割成 [“aa”,“b”] 这样两个回文子串。 示例 2: 输入:s = “a” 输出:0 示例 3: 输入:

    2024年02月15日
    浏览(45)
  • leetcode 动态规划(最后一块石头的重量II、目标和、一和零)

    力扣题目链接(opens new window) 题目难度:中等 有一堆石头,每块石头的重量都是正整数。 每一回合,从中选出任意两块石头,然后将它们一起粉碎。假设石头的重量分别为 x 和 y,且 x = y。那么粉碎的可能结果如下: 如果 x == y,那么两块石头都会被完全粉碎; 如果 x != y,那

    2024年02月03日
    浏览(46)
  • LeetCode518. 零钱兑换 II 以及 动态规划相关的排列组合问题

    一、题目 给你一个整数数组 coins 表示不同面额的硬币,另给一个整数 amount 表示总金额。 请你计算并返回可以凑成总金额的硬币组合数。如果任何硬币组合都无法凑出总金额,返回 0 。 假设每一种面额的硬币有无限个。 题目数据保证结果符合 32 位带符号整数。 示例 1: 示

    2024年02月09日
    浏览(42)
  • 【LeetCode动态规划#08】完全背包问题实战与分析(零钱兑换II)

    力扣题目链接(opens new window) 给定不同面额的硬币和一个总金额。写出函数来计算可以凑成总金额的硬币组合数。假设每一种面额的硬币有无限个。 示例 1: 输入: amount = 5, coins = [1, 2, 5] 输出: 4 解释: 有四种方式可以凑成总金额: 5=5 5=2+2+1 5=2+1+1+1 5=1+1+1+1+1 示例 2: 输入: amount = 3

    2023年04月19日
    浏览(44)

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

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

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

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

二维码1

领取红包

二维码2

领红包