算法打卡day41|动态规划篇09| Leetcode198.打家劫舍、213.打家劫舍II、337.打家劫舍 III

  算法题

Leetcode 198.打家劫舍

题目链接:198.打家劫舍

大佬视频讲解:198.打家劫舍视频讲解

 个人思路 

偷还是偷,这取决于前一个和前两个房是否被偷了,这种存在依赖关系的题目可以用动态规划解决。

解法
动态规划

动规五部曲:

1.确定dp数组(dp table)以及下标的含义

dp[i]:考虑下标i(包括i)以内的房屋,最多可以偷窃的金额为dp[i]

2.确定递推公式

决定dp[i]的因素就是第i房间偷还是不偷

  • 如果偷第i房间,那么dp[i] = dp[i - 2] + nums[i] ,即:第i-1房一定是不考虑的,找出 下标i-2(包括i-2)以内的房屋,最多可以偷窃的金额为dp[i-2] 加上第i房间偷到的钱。
  • 如果不偷第i房间,那么dp[i] = dp[i - 1],即考 虑i-1房

然后dp[i]取最大值,即dp[i] = max(dp[i - 2] + nums[i], dp[i - 1]);

3.dp数组如何初始化

从递推公式dp[i] = max(dp[i - 2] + nums[i], dp[i - 1]);可以看出,递推公式的基础就是dp[0] 和 dp[1]

从dp[i]的定义上来讲,dp[0] 一定是 nums[0],dp[1]就是nums[0]和nums[1]的最大值即:dp[1] = max(nums[0], nums[1]);

4.确定遍历顺序

dp[i] 是根据dp[i - 2] 和 dp[i - 1] 推导出来的,所以是从前到后遍历

5.举例推导dp数组

以示例二,输入[2,7,9,3,1]为例

class Solution {
	public int rob(int[] nums) {
		if (nums == null || nums.length == 0) return 0;//判空
		if (nums.length == 1) return nums[0];

		int[] dp = new int[nums.length];
		dp[0] = nums[0];
		dp[1] = Math.max(dp[0], nums[1]);//初始化

		for (int i = 2; i < nums.length; i++) {
			dp[i] = Math.max(dp[i - 1], dp[i - 2] + nums[i]);//考虑是否偷当前的
		}

		return dp[nums.length - 1];
	}
}

时间复杂度:O(n);(遍历数组)

空间复杂度:O( n);(存储一个长度为n+1的dp数组)

滚动数组优化动规
// 进一步对滚动数组的空间优化 dp数组只存与计算相关的两次数据
class Solution {
    public int rob(int[] nums) {
        if (nums.length == 1)  {
            return nums[0];
        }

        // 优化空间 dp数组只用2格空间 只记录与当前计算相关的前两个结果
        int[] dp = new int[2];
        dp[0] = nums[0];
        dp[1] = Math.max(nums[0],nums[1]);

        int res = 0;
        for (int i = 2; i < nums.length; i++) {  // 遍历
            res = Math.max((dp[0] + nums[i]) , dp[1] );
            dp[0] = dp[1];
            dp[1] = res;
        }
        return dp[1];
    }
}

时间复杂度:O(n);(遍历数组)

空间复杂度:O( 1);(无使用其他大的额外空间)


 Leetcode  213.打家劫舍II

题目链接:213.打家劫舍II

大佬视频讲解:213.打家劫舍II视频讲解

个人思路

这道题与上面那道题是类似的,只不过这里的房屋成环了,还是用动态规划解决。

解法
动态规划

对于题目中的数组,成环的话主要有如下三种情况:

  • 情况一:考虑不包含首尾元素

  • 情况二:考虑包含首元素,不包含尾元素

  • 情况三:考虑包含尾元素,不包含首元素

注意这里用的是"考虑"(情况一二三是“考虑”的范围,而具体房间偷与不偷交给递推公式去抉择

例如情况三,虽然是考虑包含尾元素,但不一定要选尾部元素! 对于情况三,取nums[1] 和 nums[3]就是最大的。而情况二 和 情况三 都包含了情况一了,所以只考虑情况二和情况三就可以了。剩下的和上面那题198打家劫舍一样的了。

​以下代码使用的了滚动数组去优化空间复杂度

class Solution {
    public int rob(int[] nums) {
        if (nums == null || nums.length == 0)//判空
            return 0;
        int len = nums.length;//数组长度
        if (len == 1)
            return nums[0];

        return Math.max(robAction(nums, 0, len - 1), robAction(nums, 1, len));//情况2,3包括情况1
    }

    int robAction(int[] nums, int start, int end) {
        int x = 0, y = 0, z = 0;
        for (int i = start; i < end; i++) {
            y = z;
            z = Math.max(y, x + nums[i]);
            x = y;
        }
        return z;
    }
}

时间复杂度:O(n);(遍历数组)

空间复杂度:O(1);(无使用其他大的额外空间)


 Leetcode 337.打家劫舍 III

题目链接:337.打家劫舍 III

大佬视频讲解:337.打家劫舍 III视频讲解

个人思路

思路不清晰...

解法
动态规划

本题可以使用动态规划,使用状态转移容器来记录状态的变化,这里可以使用一个长度为2的数组,记录当前节点偷与不偷所得到的的最大金钱。

这道题目算是树形dp的入门题目,因为是在树上进行状态转移,所以使用递归三部曲为框架,其中融合动规五部曲的内容来解题。

递归加动规

1.确定递归函数的参数和返回值,dp数组(dp table)以及下标的含义

用一个节点记录偷与不偷的两个状态所得到的金钱,那么返回值就是一个长度为2的数组即dp数组。

dp数组(dp table)以及下标的含义:下标为0记录不偷该节点所得到的的最大金钱,下标为1记录偷该节点所得到的的最大金钱

2.确定终止条件-dp数组的初始化

在遍历的过程中,如果遇到空节点的话,无论偷还是不偷都是0,所以就返回

3.确定遍历顺序

首先明确的是使用后序遍历,因为要通过递归函数的返回值来做下一步计算

通过递归左节点,得到左节点偷与不偷的金钱。

通过递归右节点,得到右节点偷与不偷的金钱。


 

4.确定单层递归的逻辑

如果是偷当前节点,那么左右孩子就不能偷,即 val1 = cur->val + left[0] + right[0]; 

如果不偷当前节点,那么左右孩子就可以偷,至于到底偷不偷一定是选一个最大的,所以:val2 = max(left[0], left[1]) + max(right[0], right[1]);

最后当前节点的状态就是{val2, val1}; 即:{不偷当前节点得到的最大金钱,偷当前节点得到的最大金钱}

5.举例推导dp数组

示例1为例,dp数组状态如下图,->用的后序遍历的方式推导

class Solution {// 状态标记递归
    public int rob(TreeNode root) {
        int[] res = robAction(root);
        return Math.max(res[0], res[1]);
    }

    int[] robAction(TreeNode root) {
        int res[] = new int[2];
        if (root == null)
            return res;

        int[] left = robAction(root.left);
        int[] right = robAction(root.right);
        
        // 不偷:Max(左孩子不偷,左孩子偷) + Max(右孩子不偷,右孩子偷)
        res[0] = Math.max(left[0], left[1]) + Math.max(right[0], right[1]);

        // 偷:左孩子不偷+ 右孩子不偷 + 当前节点偷
        res[1] = root.val + left[0] + right[0];
        return res;
    }
}

时间复杂度:O(n);(这里的n是树的高度)

空间复杂度:O( n);(输入数组大小)


 以上是个人的思考反思与总结,若只想根据系列题刷,参考卡哥的网址代码随想录算法官网

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:/a/532664.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

生鲜蔬果配送小程序开发攻略

随着互联网的快速发展&#xff0c;电商行业也在不断壮大。生鲜蔬果作为日常生活必需品&#xff0c;在线销售的需求也在不断增加。为了满足这一需求&#xff0c;开发一款生鲜蔬果配送小程序成为了必要的事情。下面就给大家介绍开发这款小程序的攻略。 1. 确定开发需求 首先&…

Java Swing游戏开发学习23

内容来自RyiSnow视频讲解 这一节讲的是Character Status角色状态或属性。 前言 这一节讲的是实现角色状态或属性的显示&#xff0c;就有点像RPG游戏中&#xff0c;人物属性显示的面板&#xff0c;其中有玩家的装备、玩家的等级&#xff0c;各种防御值、闪避值、跑速什么的。…

基于BP神经网络的分类预测模型matlab代码

基于BP神经网络的分类预测模型matlab代码&#xff0c;该数据集下&#xff0c;本模型的表现优异&#xff0c;训练集准确率可达97%&#xff0c;测试集准确率可达93.5%&#xff0c;表现优异。注释十分齐全适合新手学习。 代码获取链接&#xff1a;基于BP神经网络的分类预测模型ma…

SpringBoot3 + uniapp 对接 阿里云0SS 实现上传图片视频到 0SS 以及 0SS 里删除图片视频的操作(最新)

SpringBoot3 uniapp 对接 阿里云0SS 实现上传图片视频到 0SS 以及 0SS 里删除图片视频的操作 最终效果图uniapp 的源码UpLoadFile.vuedeleteOssFile.jshttp.js SpringBoot3 的源码FileUploadController.javaAliOssUtil.java 最终效果图 uniapp 的源码 UpLoadFile.vue <tem…

第十一届蓝桥杯省赛真题(C/C++大学B组)

试题A &#xff1a;门牌制作 #include <bits/stdc.h> using namespace std;const int N 100000; int arr[N];int main() {int ans 0,t;for(int i 1;i < 2020;i){t i;while(t > 0){if(t % 10 2) ans;t / 10;}}cout<<ans<<endl;return 0; } 试题B …

操作系统(第四周 第一堂)

目录 回顾 进程调度&#xff08;process schedule&#xff09; 进程角度 计算机整体——调度队列 队列图 调度程序 总结 回顾 上一篇文章的重点只有一个————进程 对进程的了解包含以下几个方面&#xff1a;1、程序如何变为进程 2、进程在内存中的存储形式 3、进…

Centos7配置秘钥实现集群免密登录

设备&#xff1a;MacBook Pro、多台Centos7.4服务器(已开启sshd服务) 大体流程&#xff1a;本机生成秘钥&#xff0c;将秘钥上传至服务器即可实现免密登录 1、本地电脑生成秘钥&#xff1a; ssh-keygen -t rsa -C "邮箱地址 例&#xff1a;*****.163.com"一路回车…

Bezier曲线的绘制 matlab

式中&#xff1a; 称为基函数。 。 因为n表示次数&#xff0c;点数为n1&#xff0c;显然i表示第i个控制点。 显然在Matlab中可以同矩阵的形式来计算C(u)。 关键代码为&#xff1a; clc clear % 假设控制点P取值为&#xff1a; P [4,7;13,12;19,4;25,12;30,3]; % 因此&a…

Vue2创建过程记录

提示&#xff1a;文章写完后&#xff0c;目录可以自动生成&#xff0c;如何生成可参考右边的帮助文档 文章目录 一、搭建node二、安装Vue CLI三、搭建新项目四、Elemet安装&#xff08;参照官网步骤[Element官网](https://element.eleme.cn/#/zh-CN/component/installation)&am…

Hibernate多事务同时调用update(T t) ,字段被覆盖问题

前言 今天现网有个订单卡单了&#xff0c;经过排查发现没有任何异常日志&#xff0c;根据日志定位发现本应该更新的一个状态&#xff0c;也sql肯定执行了(使用了Hibernate的ORM框架)&#xff0c;但是数据库里面的状态没有更新。大概逻辑如下 String hql from orderInfo where…

Could not resolve all files for configuration

关于作者&#xff1a;CSDN内容合伙人、技术专家&#xff0c; 从零开始做日活千万级APP。 专注于分享各领域原创系列文章 &#xff0c;擅长java后端、移动开发、商业变现、人工智能等&#xff0c;希望大家多多支持。 未经允许不得转载 目录 一、导读二、概览三、 推荐阅读 一、导…

《前端防坑》- JS基础 - 你觉得typeof nullValue === null 么?

问题 JS原始类型有6种Undefined, Null, Number, String, Boolean, Symbol共6种。 在对原始类型使用typeof进行判断时, typeof stringValue string typeof numberValue number 如果一个变量(nullValue)的值为null&#xff0c;那么typeof nullValue "?" const u …

C++的并发世界(十一)——线程池

0.线程池的概念 1.线程池使用步骤 ①初始化线程池&#xff1a;确定线程数量&#xff0c;并做好互斥访问&#xff1b; ②启动所有线程 ③准备好任务处理基类&#xff1b; ④获取任务接口&#xff1a;通过条件变量阻塞等待任务 2.atomic原子操作 std:atomic是C11标准库中的一个…

QT学习day4

widget.h #define WIDGET_H #include <QWidget> #include <QTime>//时间类 #include <QTimerEvent>//定时器类 #include <QPushButton>//按钮类 #include <QTextToSpeech>//语音播报 QT_BEGIN_NAMESPACE namespace Ui { class Widget; } QT_E…

After Effects 2024 中文激活版 高效工作流程与创新的视觉特效 mac/win

After Effects 2024是Adobe公司推出的一款专业视频特效制作软件&#xff0c;广泛应用于电影、电视、动画等媒体制作领域。它凭借强大的功能和灵活的操作&#xff0c;帮助用户轻松创建电影级影片字幕、片头和过渡效果&#xff0c;以及实现立体效果和动态场景的切换。 同时&#…

机器学习中的激活函数

激活函数存在的意义&#xff1a; 激活函数决定了某个神经元是否被激活&#xff0c;当这个神经元接收到的信息是有用或无用的时候&#xff0c;激活函数决定了对这个神经元接收到的信息是留下还是抛弃。如果不加激活函数&#xff0c;神经元仅仅做线性变换&#xff0c;那么该神经网…

【电路笔记】-逻辑或非门

逻辑或非门 文章目录 逻辑或非门1、概述2、晶体管逻辑或非门3、数字逻辑或非门类型4、通用或非门逻辑或非门是数字逻辑或门与反相器或非门串联的组合。 1、概述 或非(Not-OR)门的输出通常为逻辑电平“1”,并且仅当其任何输入处于逻辑电平“1”时才变为“低”至逻辑电平“0”…

蓝桥杯 每日2题 day4

碎碎念&#xff1a;好难好难&#xff0c;&#xff0c;发呆两小时什么也写不出来&#xff0c;&#xff0c;&#xff0c;周六大寄了 10.阶乘约数 - 蓝桥云课 (lanqiao.cn) 暴力跑了两个小时没出来结果&#xff0c;&#xff0c;去看题解要用数学&#xff1a;约数定理&#xff0c…

谈谈什么是 Redis

&#x1f525;博客主页&#xff1a;fly in the sky - CSDN博客 &#x1f680;欢迎各位&#xff1a;点赞&#x1f44d;收藏⭐️留言✍️&#x1f680; &#x1f386;慢品人间烟火色,闲观万事岁月长&#x1f386; &#x1f4d6;希望我写的博客对你有所帮助,如有不足,请指正&#…

Docker功能简单学习及使用

Docker是什么 Docker是一个快速构建&#xff0c;运行&#xff0c;管理应用的工具 传统基于linux安装程序较为复杂繁琐&#xff0c;使用docker可以快速的进行项目部署和管理 镜像与容器 Docker进行安装应用时&#xff0c;会自动搜索并下载应用镜像(image)。镜像不仅包含应用本…