198. 打家劫舍--动态规划

名字是乱打的

发布于 2021-12-24 08:30:23

2550

发布于 2021-12-24 08:30:23

文章被收录于专栏：软件工程

题目:

你是一个专业的小偷，计划偷窃沿街的房屋。每间房内都藏有一定的现金，影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。给定一个代表每个房屋存放金额的非负整数数组，计算你不触动警报装置的情况下，一夜之内能够偷窃到的最高金额。示例 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 。提示： 1 <= nums.length <= 100 0 <= nums[i] <= 400 Related Topics 数组动态规划

思路:

动态规划的的四个解题步骤是：

定义子问题
写出子问题的递推关系
确定 DP 数组的计算顺序
空间优化（可选）

该思路来自于leetcode上一个老哥写的非常详细的动态规划思路,可以看原文

代码:

class Solution {
        //f(k)=max(f(k-1),(f(k-2)+curr))
        public int rob(int[] nums) {
            if (nums.length==0){
                return 0;
            }
            final int length = nums.length;
            int[] money=new int[length+1];
            money[0]=0;
            money[1]=nums[0];
            for (int i = 2; i <= length; i++) {
                money[i]=Math.max(money[i-1],(money[i-2]+nums[i-1]));
            }

            return money[length];
        }
    }

空间优化后代码:

空间优化是动态规划问题的进阶内容了。对于初学者来说，可以不掌握这部分内容。

空间优化的基本原理是，很多时候我们并不需要始终持有全部的 DP 数组。对于小偷问题，我们发现，最后一步计算 f(n)f(n) 的时候，实际上只用到了 f(n-1)f(n−1) 和 f(n-2)f(n−2) 的结果。n-3n−3 之前的子问题，实际上早就已经用不到了。那么，我们可以只用两个变量保存两个子问题的结果，就可以依次计算出所有的子问题。

class Solution {
        //f(k)=max(f(k-1),(f(k-2)+curr))
        public int rob(int[] nums) {
            if (nums.length==0){
                return 0;
            }
            final int length = nums.length;
            int ppre=0,pre=nums[0], curr=nums[0];
            for (int i = 2; i <= length; i++) {
                curr =Math.max(pre,(ppre+nums[i-1]));
                ppre=pre;
                pre= curr;
            }

            return curr;
        }
    }

本文参与腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。

原始发表：2021/11/13 ，如有侵权请联系 cloudcommunity@tencent.com 删除

编程算法

本文分享自作者个人站点/博客前往查看

如有侵权，请联系 cloudcommunity@tencent.com 删除。

本文参与腾讯云自媒体同步曝光计划，欢迎热爱写作的你一起参与！

编程算法

登录后参与评论

0 条评论

热度