美文网首页
P46-打家劫舍-动态规划-迭代

P46-打家劫舍-动态规划-迭代

作者: YonchanLew | 来源:发表于2021-05-29 22:44 被阅读0次
//打家劫舍
/*
* 你是一个专业的小偷,计划偷窃沿街的房屋。每间房内都藏有一定的现金,影响你偷窃的唯一制约因素就是
* 相邻的房屋装有相互连通的防盗系统,如果两间相邻的房屋在同一晚上被小偷闯入,系统会自动报警。
* 给定一个代表每个房屋存放金额的非负整数数组,计算你 不触动警报装置的情况下,一夜之内能够偷窃到的最高金额
* */
public class P47 {
    public static void main(String[] args) {
//        int[] nums = new int[]{1,2,3,1};        //4
        int[] nums = new int[]{2,7,9,3,1};        //12
        System.out.println(maxMoney(nums, nums.length-1));
        System.out.println(maxMoney2(nums));
        System.out.println(maxMoney3(nums));
    }

    //递归
    public static int maxMoney(int[] nums, int index){
        if(nums == null || index < 0){  //递归出口
            return 0;
        }
        if(index == 0){
            return nums[0];
        }

        //递推公式,i-1 和 i-2+nums[i]的最优解
        return Math.max(maxMoney(nums, index-1), maxMoney(nums, index-2)+nums[index]);
    }

    //存在重复计算,左边会递归i-1,i-2,i-3,右边也同样i-2、i-3...
    //把递归的陪一次记录存起来,就是动态规划中的DP数组
    //用递归就是dp有值得时候直接取,没值得时候递归,就避免重复递归的问题

    //动态规划-迭代(不用递归)
    public static int maxMoney2(int[] nums){
        int length = nums.length;
        if(nums == null || length == 0){
            return 0;
        }
        if(length == 1){
            return nums[0];
        }

        int[] dp = new int[nums.length];
        dp[0] = nums[0];
        dp[1] = Math.max(nums[0], nums[1]);
        //有了0和1这两个数,就可以推断其他数
        //迭代
        for(int i=2; i<length; i++){
            dp[i] = Math.max(dp[i-1], dp[i-2]+nums[i]);     //递推公式
        }

        return dp[length-1];        //最后位置就是最优解
    }

    //上面的方法占用空间复杂度高,有些数据存起来但又不使用
    //优化
    public static int maxMoney3(int[] nums){
        int length = nums.length;
        if(nums == null || length == 0){
            return 0;
        }
        if(length == 1){
            return nums[0];
        }

        int first = nums[0];
        int second = nums[1];
        for(int i=2; i<length; i++){
            int temp = second;
            second = Math.max(first+nums[i], second);
            first = temp;
        }

        return second;
    }
}

相关文章

  • P46-打家劫舍-动态规划-迭代

  • 动态规划——打家劫舍

    这道题也算是一道挺经典的题,即使不了解动态规划的人肯定也见过这道题。先来看代码 这里还有第二种解法,算法思想依然是...

  • [动态规划]-打家劫舍

    你是一个专业的小偷,计划偷窃沿街的房屋。每间房内都藏有一定的现金,影响你偷窃的唯一制约因素就是相邻的房屋装有相互连...

  • 2022-02-19 动态规划高频题专题【1】

    动态规划基本类型 dp基础 背包问题 打家劫舍 股票问题 子序列问题 进阶动态规划 深入理解动态规划过程 定义dp...

  • 动态规划之——打家劫舍

    LeetCode198. 打家劫舍 题目描述: 你是一个专业的小偷,计划偷窃沿街的房屋。每间房内都藏有一定的现金,...

  • 动态规划之打家劫舍

    题目 你是一个专业的小偷,计划偷窃沿街的房屋.每间房内都藏有一定的现金,影响你偷窃的唯一制约因素就是相邻的房屋装有...

  • 动态规划(六)

    这一次我们来看看动态规划中打家劫舍这一类的问题,在LeetCode中这类问题有:第198题:打家劫舍 https:...

  • LeetCode-打家劫舍(动态规划)

    题目链接 => 戳这里 解法

  • 初级算法-动态规划-打家劫舍

    你是一个专业的小偷,计划偷窃沿街的房屋。每间房内都藏有一定的现金,影响你偷窃的唯一制约因素就是相邻的房屋装有相互连...

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

    题目: 你是一个专业的小偷,计划偷窃沿街的房屋。每间房内都藏有一定的现金,影响你偷窃的唯一制约因素就是相邻的房屋装...

网友评论

      本文标题:P46-打家劫舍-动态规划-迭代

      本文链接:https://www.haomeiwen.com/subject/bauojltx.html