经典动态规划题——打家劫舍

简介: 前端西瓜哥

大家好,我是前端西瓜哥。

今天我们做一道非常经典的动态规划题——打家劫舍,适合用来入门动态规划。

题目描述

题目:你是一个专业的小偷,计划偷窃沿街的房屋。每间房内都藏有一定的现金,影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统,如果两间相邻的房屋在同一晚上被小偷闯入,系统会自动报警。

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


示例:

输入:[1,2,3,1]

输出:4

解释:偷窃 1 号房屋 (金额 = 1) ,然后偷窃 3 号房屋 (金额 = 3)。     偷窃到的最高金额 = 1 + 3 = 4 。

解题

动态规划(dynamic programming)是一个将问题拆分成子问题,通过解决子问题最终解决原问题的一种解法。

和分治法的子问题相互独立不同,动态规划的子问题是重叠的,多个子问题可能依赖相同的一个子子问题。

动态规划(dynamic programming)的 programming 指的是 “表格”,因为我们经常会构建一个二维数组来记录每个阶段的变化。有时候我们不需要记录过去阶段的状态,倒是可以改用一维数组,降低一下空间复杂度。

动态规划题的解法通常有两种实现方式:

  1. 迭代(自底向上)
  2. 递归 + 备忘录(自顶向下)

接下来我们就用这两种方式来解题。

迭代法

迭代法,需要用到状态转移表,就是前面提到的 programming(表格),来记录子问题向父问题的状态转移变化。

根据题意的限制,相邻的房屋不能同时选择,所以对于第 i 个房屋,我们有两种方案:

  1. 选择抢当前房屋,将抢到的金额,加上到抢到前前一个房间的最大金额
  2. 不选择当前房屋,此时金额为抢到前一个房屋时的最大金额

这两种选择,选择其中金额大的,就是抢到第 i 个房屋的最大金额。

我们的的状态转移方程式为:

dp[i] = Max(dp[i - 1], dp[i - 1] + curRob)

代码实现如下:

function rob(nums): number {
  if (nums.length === 0) return 0;
  if (nums.length === 1) return nums[0];
  const dp = new Array(nums.length);
  dp[0] = nums[0];
  dp[1] = Math.max(nums[0], nums[1]);
  for (let i = 2; i < nums.length; i++) {
    dp[i] = Math.max(dp[i - 1], dp[i - 2] + nums[i]);
  }
  return dp[dp.length - 1];
};

这里需要初始化 dp[0] 和 dp[1],否则我们的 dp[i - 2] 就会越界。

时间复杂度 O(n),空间复杂度 O(n)。

对于初始化,还有更优雅的写法:

function rob(nums): number {
  const n = nums.length;
  const dp = new Array(n + 2);
  dp[n] = 0;
  dp[n + 1] = 0;
  for (let i = n - 1; i >= 0; i--) {
    dp[i] = Math.max(nums[i] + dp[i + 2], dp[i + 1]);
  }
  return dp[0];
};

我们给状态数组末尾多加两个值为 0 的数组元素,然后逆向迭代数组元素。这样就不需要初始化最前面的两个元素了。

优雅,实在是优雅。

读者可能也观察到了,其实我们这个代码实现并不需要整个数组元素,只需要两个元素就够了。

function rob(nums): number {
  const n = nums.length;
  let lo = 0;
  let hi = 0;
  for (let i = n - 1; i >= 0; i--) {
    const cur = Math.max(nums[i] + lo, hi);
    lo = hi;
    hi = cur;
  }
  return hi;
};

这样,时间复杂度就又从 O(n) 下降到了 O(1),已经是最优解。

递归 + 备忘录

思路依旧是迭代的思路,只是换成了递归的形式。

function rob(nums): number {
  const memo = new Array(nums.length);
  return robByIndex(nums, memo, nums.length - 1);
};
function robByIndex(nums, memo, i): number {
  if (i < 0) return 0;
  if (memo[i] !== undefined) return memo[i];
  memo[i] = Math.max(
    robByIndex(nums, memo, i - 1),
    robByIndex(nums, memo, i - 2) + nums[i]
  )
  return memo[i];
}

memo 备忘录的作用是缓存,因为多个子问题可能依赖相同的子子问题,会导致很多重复的迭代。如果不做缓存,就变成回溯了,时间复杂度非常高。

这种解法因为用了备忘录做了很多剪枝,时间复杂度其实也是 O(n)。

因为使用了备忘录,并有多层调用栈,空间复杂度是 O(n)。

总结

动态规划的常规解法有两种。

一种是构造 programming,即表格,通常为二维数组,记录迭代过程中的状态。二维数组可以根据实际情况,降维为一维数组或几个变量,本文的题目就成功降低维度为两个变量。

还有一种是递归的方式,因为动态规划的问题通常会有重叠的子问题,所以我们往往需要一个备忘录记录我们曾经走过的路。

如果没有备忘录,其实就是回溯了,时间复杂度会高很多。

回溯问题多为找所有解的问题,所以并不会有重复递归的情况。而动态规划多为求最值问题,只需要知道递归的最值就行了,其中有什么组合我们并不关心,所以要用备忘录。

当然,上面这些都是实现套路,动态规划最难的是找出状态转移方程式,即应该通过怎样的维度将问题做拆分,并找出当前阶段的状态怎么通过之前阶段的状态转移过来。

我是打算每周一到周五做五道算法题,结果常常是周六日连做五道的前端西瓜哥。

欢迎关注我,学习更多的前端和算法相关的知识。

相关文章
|
关系型数据库 MySQL 数据挖掘
MYSQL日期与时间函数的实用技巧
MYSQL日期函数与时间函数是数据库操作的关键工具,可轻松处理、查询、比较和格式化日期时间数据。它们能提取日期的年、月、日等部分,便于筛选和统计;同时,也能处理时间数据,如计算时间差、获取当前时间,助力用户更好地管理时间信息。掌握这些函数,不仅能提升数据库操作效率,还能为数据分析和报表生成提供有力支持。无论初学者还是资深数据库管理员,精通MYSQL的日期和时间函数都至关重要,以满足各种数据处理需求,确保数据的准确性和高效性。
674 0
|
监控 关系型数据库 数据库
rds的安全性
rds的安全性
461 7
|
XML 存储 数据可视化
XML DTD原理及使用
是一种可扩展的标记语言,用于存储和交换数据,它被设计成具有简单、易于理解的格式,并能够方便地在不同的系统和应用程序之间共享数据。XML的语法规则类似于HTML,但XML的目的不仅仅是用于显示数据,更是用于描述数据的结构和关系。与HTML相比,XML更加严格和规范,它需要通过或RELAX NG等方式定义文档的结构,同时还可以使用命名空间和XSLT等技术来处理和转换XML文档。独立于任何特定的操作系统、平台或开发环境。可以与许多不同的编程语言和应用程序进行交互。
|
存储 网络协议 API
「译文」CMDB 最佳实践技术指南 -2- 主流的 CMDB 发现技术
「译文」CMDB 最佳实践技术指南 -2- 主流的 CMDB 发现技术
|
机器学习/深度学习 文字识别 算法
【OCR学习笔记】2、OCR图像预处理(上)
【OCR学习笔记】2、OCR图像预处理(上)
1756 0
|
分布式计算 Java Go
Golang深入浅出之-Go语言中的分布式计算框架Apache Beam
【5月更文挑战第6天】Apache Beam是一个统一的编程模型,适用于批处理和流处理,主要支持Java和Python,但也提供实验性的Go SDK。Go SDK的基本概念包括`PTransform`、`PCollection`和`Pipeline`。在使用中,需注意类型转换、窗口和触发器配置、资源管理和错误处理。尽管Go SDK文档有限,生态系统尚不成熟,且性能可能不高,但它仍为分布式计算提供了可移植的解决方案。通过理解和掌握Beam模型,开发者能编写高效的数据处理程序。
394 1
|
Web App开发 JSON 缓存
HTTP的请求方法,空行,body,介绍请求报头的内部以及粘包问题
HTTP的请求方法,空行,body,介绍请求报头的内部以及粘包问题
|
弹性计算 应用服务中间件
阿里云服务器最新价格汇总,新用户和老用户新购折扣及优惠价格
阿里云新用户和老用户新购云服务器可享受什么折扣及具体优惠价格是多少是大家在购买云服务器时最关心的问题,目前阿里云活动中的云服务器有轻量应用服务器及通用算力型u1、计算型c7、通用型g7、内存型r7和最新第八代计算型c8y、通用型g8y、内存型r8y实例云服务器,折扣有1.5折、3.1折、3折、6折、7.2折和8.5折,新用户和老用户可享受的折扣与价格是不一样的,为此,小编特惠整理了一份阿里云新用户和老用户新购云服务器最新折扣及优惠价格,以供大家参考和选购。
阿里云服务器最新价格汇总,新用户和老用户新购折扣及优惠价格
|
前端开发
前端学习案例2-文件上传的例子用状态模式优化3
前端学习案例2-文件上传的例子用状态模式优化3
96 0
前端学习案例2-文件上传的例子用状态模式优化3
|
存储 弹性计算 安全
使用ECS部署Github开源项目以及架设应用程序服务器的体验报告
使用ECS部署Github开源项目Mcsmanager以及架设Minecraft服务器(作业用)的体验以及经验分享
使用ECS部署Github开源项目以及架设应用程序服务器的体验报告