【动态规划专题】LeetCode 198. 打家劫舍-跟着帅地玩副业，开拓第二曲线PlayOffer

宁永久会员 2023年3月14日下午5:00

递推关系

class Solution {
    public int rob(int[] nums) {
        int len = nums.length;
        if(len == 1){
            return nums[0];
        }
        int[] dp = new int[len];
        dp[0] = nums[0];
        dp[1] = Math.max(nums[0], nums[1]);
        for(int i = 2; i < len; i++){
            dp[i] = Math.max(dp[i - 2] + nums[i], dp[i - 1]);
        }
        return dp[len - 1];
    }
}

0 赞同 0 条回复

PatNick 普通 2023年1月20日下午7:43

# dp为一维数组
def rob(nums: list[int]) -> int:
    if len(nums) == 0:
        return 0
    if len(nums) == 1:
        return nums[0]

    dp = [0] * len(nums)

    # dp[i]是i时盗窃的最高金额
    dp[0] = nums[0]
    dp[1] = max(nums[0], nums[1])

    for i in range(2, len(nums)):
        dp[i] = max(dp[i - 2] + nums[i], dp[i - 1])

    return dp[-1]



# 将空间复杂度优化为O（1）
# dp为单变量，同时还需要一个变量保存i-2的数据
def rob(nums: list[int]) -> int:
    if len(nums) == 0:
        return 0
    if len(nums) == 1:
        return nums[0]

    p = nums[0]
    dp = max(nums[0],nums[1])

    # dp[i]是i时盗窃的最高金额


    for i in range(2, len(nums)):
        temp = dp
        dp = max(p + nums[i], dp)
        p = temp


    return dp

0 赞同 0 条回复

lucca 普通 2023年1月19日下午10:58

终于会一道

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

0 赞同 0 条回复

@ 普通 2022年12月31日上午11:34

class Solution {
    //时间复杂的：O(N)  空间复杂度：O(N)
    public int rob(int[] nums) {
        if (nums.length == 1)
            return nums[0];

        int[] dp = new int[nums.length];

        dp[0] = nums[0];
        dp[1] = Math.max(nums[0], nums[1]);

        for (int i = 2; i < nums.length; i++) {
            dp[i] = Math.max(dp[i - 1], dp[i - 2] + nums[i]);
        }

        return dp[nums.length - 1];
    }

    //优化，空间辅助度为O(1);
    //时间复杂的：O(N)  空间复杂度：O(1)
     public int rob2(int[] nums) {
        if (nums == null || nums.length == 0) {
            return 0;
        }
        int length = nums.length;
        if (length == 1) {
            return nums[0];
        }
        int first = nums[0], second = Math.max(nums[0], nums[1]);
        for (int i = 2; i < length; i++) {
            int temp = second;
            second = Math.max(first + nums[i], second);
            first = temp;
        }
        return second;
    }


}

0 赞同 0 条回复

y 普通 2022年12月3日下午6:16

var rob = function(nums) {
  if (nums.length === 0) return;
  const dp = [];
  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 - 2] + nums[i], dp[i - 1])
  }
  return dp[nums.length - 1]
};

动态规划

0 赞同 0 条回复

T 普通 2022年12月3日上午10:10

动态规划，dp[i]当前表示前i天最大收益

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

0 赞同 0 条回复

symbol 普通 2022年12月3日上午7:57

func rob(nums []int) int {
    //特殊情况
    if len(nums)<1{
        return 0
    }
    if len(nums)==1{
        return nums[0]
    }
    if len(nums)==2{
        return max(nums[0],nums[1])
    }
    dp :=make([]int,len(nums))
    dp[0]=nums[0]
    dp[1]=max(nums[0],nums[1])
    for i:=2;i<len(nums);i++{
        dp[i]=max(dp[i-2]+nums[i],dp[i-1]) //转移数组
    }
    return dp[len(dp)-1]
}

func max(a, b int) int {
    if a>b{
        return a
    }
    return b
}

0 赞同 0 条回复

Tolkien 永久会员 2022年12月1日下午9:03

/**
     * 方法一：动态规划
     * 时间复杂度：O(n), 空间复杂度：O(n)
     * 1. 前i个房屋，一夜之间能偷窃的最高金额
     * 2. 偷第i个房屋，dp[i][1] = dp[i-1][0] + nums[i]; 不偷第i个房屋，dp[i][0] = max(dp[i-1][1], dp[i-1][0])
     * 3. dp[0][0]=0 dp[0][1]=nums[0]
     */
    public int rob(int[] nums) {
        int n = nums.length;
        int[][] dp = new int[n][2];
        dp[0][0] = 0; dp[0][1] = nums[0];

        for (int i = 1; i < n; i++) {
            dp[i][1] = dp[i-1][0] + nums[i];
            dp[i][0] = max(dp[i-1][1], dp[i-1][0]);
        }

        return Math.max(dp[n-1][0], dp[n-1][1]);
    }

    /**
     * 方法二：动态规划 优化
     * 时间复杂度：O(n), 空间复杂度：O(1)
     */
    public static int rob2(int[] nums) {
        int n = nums.length;
        int[] dp = new int[2];

        dp[0] = 0; dp[1] = nums[0];

        for (int i = 1; i < n; i++) {
            int temp = dp[0] + nums[i];
            dp[0] = Math.max(dp[1], dp[0]);
            dp[1] = temp;
        }

        return Math.max(dp[0], dp[1]);
    }

0 赞同 0 条回复

訁訁訁訁訁普通 2022年11月30日下午11:10

class Solution {
    public int rob(int[] nums) {
        int n = nums.length;
        if (n == 0) return 0;
        if (n == 1) return nums[0];
        int[] dp = new int[n];
        dp[0] = nums[0];//表示考虑第0间房子
        dp[1] = Math.max(nums[0],nums[1]);//考虑第0间和第1间的最大值
        for (int i = 2;i < n; i++) {
            //状态转移方程表示：第i个房屋的最大金额dp[i]:
            //1.如果偷第i间的话，表示不能投第i-1间（即金额等于到i-2的最大金额加第i间房屋的金额
            //2.如果不偷第i间的话，金额应该等于到第i-1间的金额
            dp[i] = Math.max(nums[i]+dp[i-2],dp[i-1]);
        }
        return dp[n - 1];
    }
}

0 赞同 0 条回复

Mooby 普通 2022年11月29日下午10:05

class Solution {
    public int rob(int[] nums) {
        if (nums == null || nums.length == 0) {
            return 0;
        }
        int length = nums.length;
        if (length == 1) {
            return nums[0];
        }
        int[] dp = new int[length];
        dp[0] = nums[0];
        dp[1] = Math.max(nums[0], nums[1]);
        for (int i = 2; i < length; i++) {
            dp[i] = Math.max(dp[i - 2] + nums[i], dp[i - 1]);
        }
        return dp[length - 1];
    }
}

时间：O(1)，空间：O(n)

0 赞同 0 条回复

青木普通 2022年11月28日下午9:46

/**
    感觉还得动笔才能算清楚
    dp中i-1位置只需要保持最高的钱数就可以了，i位置只需要比较i-1位置和i-2与i的和 就可以了
    当然还可以优化，因为大部分的dp数组都没有用上，优化的话只需要维护i-2和i-1位置的就可以了

    空间O(1)
    时间O(n)
 */

class Solution {
    public int rob(int[] nums) {
        // int[] dp = new int[nums.length+1];
        // dp[1] = nums[0];
        // for(int i=1; i<nums.length; i++){
        //     dp[i+1] = Math.max(dp[i], dp[i-1] + nums[i]);
        // }
        // return dp[nums.length];

        // 空间优化
        int dp1=0, dp2=nums[0];
        for(int i=1; i<nums.length; i++){
            int dp = Math.max(dp2, dp1+nums[i]);
            dp1 = dp2;
            dp2 = dp;
        }
        return dp2;
    }
}

0 赞同 0 条回复

西西弗斯的石头永久会员 2022年11月28日下午8:36

时间空间复杂度为O（n）

class Solution {
    public int rob(int[] nums) {
        if(nums.length == 1) return nums[0];
        int[] dp = new int[nums.length];
        dp[0] = nums[0];
        // 2 1 1 2 这里设置初始值需要注意
        dp[1] = Math.max(nums[0],nums[1]);
        for(int i = 2;i < nums.length;i++){
            dp[i] = Math.max(dp[i-1],dp[i-2]+nums[i]);
        }
        return dp[nums.length - 1];
    }
}

0 赞同 0 条回复

【动态规划专题】LeetCode 198. 打家劫舍

共以下 12 个回答

终于会一道

# 回答此问题取消回复

【动态规划专题】LeetCode 198. 打家劫舍

共以下 12 个回答

终于会一道

# 回答此问题 取消回复

# 回答此问题取消回复