首页 > 编程语言 >day52 动态规划part9 代码随想录算法训练营 213. 打家劫舍 II

day52 动态规划part9 代码随想录算法训练营 213. 打家劫舍 II

时间:2024-03-03 14:00:23浏览次数:41  
标签:return 213 nums rob 随想录 len II dp

题目:213. 打家劫舍 II

我的感悟:

  • 看了题解不难,就是环这个思路转化很重要!

理解难点:

  • 环的转化为,首,尾。
  • 代码上面可以省略长度为2的校验

听课笔记:

  • 分3中情况:
  • 不考虑首尾 | 考虑首 | 考虑尾
  • 而情况2和情况3 包含了情况1

我的代码:

class Solution:
    def rob(self, nums: List[int]) -> int:
        if len(nums) == 1:
            return nums[0]
        # if len(nums) == 2:
        #     return max(nums[0],nums[1])
        # 情况2:只包含首元素
        res1 = self.rob_base(nums[:len(nums)-1])
        # 情况3:只包含尾元素
        res2 = self.rob_base(nums[1:])
        return max(res1,res2)
    
    def rob_base(self,nums):
        if len(nums) == 0:
            return 0
        if len(nums) == 1:
            return nums[0]
        dp = [0] *len(nums)
        dp[0] = nums[0]
        dp[1] = max(nums[0],nums[1])
        for i in range(2,len(nums)):
            dp[i] = max(dp[i-1],nums[i]+dp[i-2])
        # print(dp)
        return dp[-1]

通过截图:

老师代码:

python网友没我写的好

扩展写法:

资料:

 213.打家劫舍II  

视频讲解:https://www.bilibili.com/video/BV1oM411B7xq

https://programmercarl.com/0213.%E6%89%93%E5%AE%B6%E5%8A%AB%E8%88%8DII.html

标签:return,213,nums,rob,随想录,len,II,dp
From: https://www.cnblogs.com/liqi175/p/18049963

相关文章

  • 代码随想录 第11天 | 20. 有效的括号 ● 1047. 删除字符串中的所有相邻重复项 ● 150.
    Leetcode:20.有效的括号-力扣(LeetCode)思路:就是用栈存左右括号,都为0就说明true,不为零说明有没有匹配成功的括号,是false,思路没有问题,时间超时了,还得用C++...,java更好的思路如下:如果是左括号,push右括号,如果是右括号,判断是否与栈顶元素匹配,JAVA//deque.isEmpty();这个方法返回......
  • 力扣80.删除排序数组中的重复项 II
    题目:给你一个有序数组nums,请你删除重复出现的元素,使得出现次数超过两次的元素只出现两次,返回删除后数组的新长度。实现方法:使用map计数,用快慢指针方法,快指针不断加一,慢指针在计数小于出现次数时加一,再将快指针指向的数赋给慢指针指向的数。funcremoveDuplicates(nums......
  • 数组(基于代码随想录)的随笔
    数组数组基础知识数组是存放在连续内存空间上的相同类型数据的集合。数组的元素是不能删的,只能覆盖。那么二维数组在内存的空间地址是连续的么?Java的二维数组在内存中不是3*4的连续地址空间,而是四条连续的地址空间组成!数组的经典题目二分法二分法时间复杂度:O(logn)......
  • 洛谷题单指南-二分查找与二分答案-P1182 数列分段 Section II
    原题链接:https://www.luogu.com.cn/problem/P1182题意解读:每段和的最大值越小,则分段数就越多,因此可以通过给定每段和的最大值,将分段数划分为两类:<=M,>M,对每段和的最大值进行二分即可。解题思路:二分的判定条件为,给定每段和的最大值,计算分段数,计算逻辑如下:依次遍历每一个数,求当前......
  • 代码随想录算法训练营第三十四天| ● 860.柠檬水找零 ● 406.根据身高重建队列 ●
    柠檬水找零 题目链接:860.柠檬水找零-力扣(LeetCode)思路:注意对于20元的情况,有两种找零方式,            头一次见到这种情况,随便加一个标准输出才能通过的样例。classSolution{public:boollemonadeChange(vector<int>&bills){in......
  • 代码随想录算法训练营day11 | leetcode 20. 有效的括号、1047. 删除字符串中的所有相
    目录题目链接:20.有效的括号-简单题目链接:1047.删除字符串中的所有相邻重复项-简单题目链接:150.逆波兰表达式求值-中等题目链接:20.有效的括号-简单题目描述:给定一个只包括'(',')','{','}','[',']'的字符串s,判断字符串是否有效。有效字符串需满足:左括号必须用相同类型的右......
  • 代码随想录 第十天 | ● 理论基础 ● 232.用栈实现队列 ● 225. 用队列实现栈
    队列的方法:添加元素:add(Ee):将指定的元素添加到队列的尾部,如果队列已满则抛出异常。offer(Ee):将指定的元素添加到队列的尾部,如果队列已满则返回false。移除元素:remove():移除并返回队列的头部元素,如果队列为空则抛出异常。poll():移除并返回队列的头部元素,如果......
  • 代码随想录 第九天 | 烤馍片(kmp)算法 ●28. 实现 strStr() ●459.重复的子字符串
    烤馍片算法(kmp):为了不让遍历的指针回退,每次不相等的时候找不相等之前的字符串的最长相等前后缀。i表示目标字符串,j表示需要在目标找到的字符串的指针。最长相等前后缀的长度就是之前有多少个与needle字符串相同,直接将j跳到上一元素位置记录的最长相等前后缀长度(next数组),这样i就可以......
  • STM32硬件IIC使用
    STM32硬件IIC使用.md概述虽然STM32的硬件IIC据说有设计缺陷,但是经过我的实践,至少STM32F103的硬件IIC是没问题的。这里给出STM32的硬件IIC的使用以及编程思路。1.STM32硬件IIC引脚在这里给出STM32F103的硬件IIC引脚,方便查阅使用2.STM32硬件IIC使用流程STM32的硬件IIC我认......
  • IIS10 隐藏 http server、删除 Windows Server IIS 10 和 ASP.NET 中的 HTTP 响应标头
    一、方案1IIS10.0中的removeServerHeaderrequestFiltering在IIS10.0(WindowsServer2016/2019)中,您可以通过在system.webServer节点中配置requestFiltering来移除Server标头:web.config<security><requestFilteringremoveServerHeader="true"/></securit......