培训学校网站建设要点,网站扁平化设计风格,网络优化工作内容,喜迎二十大演讲稿大家好#xff0c;我是晴天学长#xff0c;准备开始深入动态规划啦#xff0c;先从记忆化搜索开始#xff0c;需要的小伙伴可以关注支持一下哦#xff01;后续会继续更新的。#x1f4aa;#x1f4aa;#x1f4aa; 1) .打家劫舍 你是一个专业的小偷#xff0c;计划偷窃…大家好我是晴天学长准备开始深入动态规划啦先从记忆化搜索开始需要的小伙伴可以关注支持一下哦后续会继续更新的。 1) .打家劫舍 你是一个专业的小偷计划偷窃沿街的房屋。每间房内都藏有一定的现金影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统如果两间相邻的房屋在同一晚上被小偷闯入系统会自动报警。
给定一个代表每个房屋存放金额的非负整数数组计算你 不触动警报装置的情况下 一夜之内能够偷窃到的最高金额。
示例 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)。
提示
1 nums.length 100 0 nums[i] 400 2) .算法思路
纯dfs也可以但是会超时。所以用到了记忆化搜索。用一个数组简单的记录搜索的答案进行返回。只关注现在的状态和上一步的状态。 3) .算法步骤
1.定义一个私有的数组 nums 和 memo用于存储输入的房屋金额和记忆化搜索的结果。 2.创建 rob 方法来启动算法。在该方法中初始化 nums 和 memo 数组并将 memo 数组的所有元素初始化为 -1。 3.调用 dfs 方法将起始索引设为 nums.length - 1最后一个房屋并返回结果。 4.在 dfs 方法中首先检查是否已经搜索过当前索引 i 的结果。如果在 memo 数组中存在已计算的值则直接返回该值作为结果避免重复计算。 1如果当前索引 i 小于 0表示没有可选的房屋可偷窃返回 0。 否则根据动态规划的思想选择在当前房屋偷窃或者不偷窃的最大值。2使用递归调用 dfs 方法分别计算不偷窃当前房屋的结果即 dfs(i - 1)和偷窃当前房屋的结果即 dfs(i - 2) nums[i]。 3取两种情况的最大值作为当前索引 i 的结果并将其存储在 memo 数组中以备后续使用。 4返回当前索引 i 的结果作为最终答案。 4.代码示例 class Solution {private int[] nums, memo;public int rob(int[] nums) {this.nums nums;this.memo new int[nums.length];Arrays.fill(memo, -1);return dfs(nums.length - 1);}private int dfs(int i) {//出口if (i 0) return 0;// 看是否已经搜索过if (memo[i] ! -1) {return memo[i];}int result Math.max(dfs(i - 1), dfs(i - 2) nums[i]);memo[i] result;return result;}}5.总结
转移方程怎么写。 试题链接
