Rust面试宝典第4题：打家劫舍

题目

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

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

        示例 1：

输入：[1,2,3,1]输出：4解释：偷窃1号房屋 (金额 = 1) ，然后偷窃3号房屋 (金额 = 3)，偷窃到的最高金额为1 + 3 = 4。

        示例 2：

输入：[2,7,9,3,1]输出：12解释：偷窃1号房屋 (金额 = 2), 偷窃3号房屋 (金额 = 9)，接着偷窃5号房屋 (金额 = 1)，偷窃到的最高金额为2 + 9 + 1 = 12。

解析

        这道题主要考察应聘者对动态规划算法的理解和应用能力，在面试中比较常见。

        首先，我们要明确问题的限制条件和目标。在这个问题中，小偷不能偷相邻的房屋，因为相邻的房屋装有连通的防盗系统，如果两间相邻的房屋在同一晚上被闯入，系统会自动报警

本文链接：https://www.kjpai.cn/news/2024-04-21/160829.html，文章来源：网络cs，作者：晨起，版权归作者所有，如需转载请注明来源和作者，否则将追究法律责任！