题解 | #打家劫舍(一)#

打家劫舍(一)

http://www.nowcoder.com/practice/c5fbf7325fbd4c0ea3d0c3ea6bc6cc79

一、思路

动态规划:

  1. 确定属性:dp[i]dp[i]表示从数组下标为00的房间开始到达数组下标为ii的房间此时所能获得的最多的偷窃金额。
  2. 确定边界条件: dp[0]=nums[0]dp[0] = nums[0]
  3. 确定状态转移方程: dp[i]=max(dp[i2]+nums[i],dp[i1])dp[i] = max(dp[i - 2] + nums[i], dp[i - 1])
  4. 确定结果值:假定nnnumsnums数组的长度,dp[n1]dp[n - 1]即为从数组下标为00的房间开始到达数组下标为n1n -1的房间此时所能获得的最多的偷窃金额。也就是题目要求的,因此我们最后返回dp[n1]dp[n - 1]即可。

二、代码

初步代码

import java.util.*;

public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可
     *
     * 
     * @param nums int整型一维数组 
     * @return int整型
     */
    public int rob (int[] nums) {
        int n = nums.length;
        if (n == 1) {
            return nums[0];
        }
        int[] dp = new int[n];
        dp[0] = nums[0];
        dp[1] = Math.max(nums[0], nums[1]);
        for (int i = 2; i < n; i++) {
            dp[i] = Math.max(dp[i - 2] + nums[i], dp[i - 1]);
        }
        return dp[n - 1];
    }
}

此时时间复杂度是O(n)O(n),空间复杂度是O(n)O(n)

优化后的代码

我们可以发现dp[i]dp[i]只跟之前两次的状态有关,因此我们可以不用创建O(n)O(n)空间的复杂度,可以用滚动数组代替,优化空间复杂度为O(1)O(1)

JavaJava代码

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可
     *
     * 
     * @param nums int整型一维数组 
     * @return int整型
     */
    public int rob (int[] nums) {
        // write code here
        int n = nums.length;
        if (n == 1) {
            return nums[0];
        }
        int a = nums[0];
        int b = Math.max(nums[0], nums[1]);
        int sum = 0;
        for (int i = 2; i < n; i++) {
            int tmp = b;
            b = Math.max(a + nums[i], b);
            a = tmp;
        }
        return b;
    }
}

CC++代码

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可
     *
     * 
     * @param nums int整型vector 
     * @return int整型
     */
    int rob(vector<int>& nums) {
        // write code here
        int n = nums.size();
        if (n == 1) {
            return nums[0];
        }
        int a = nums[0];
        int b = max(nums[0], nums[1]);
        for (int i = 2 ; i < n; i++) {
            int tmp = b;
            b = max(nums[i] + a, b);
            a = tmp;
        }
        return b;
    }
};

python3python3 代码


class Solution:
    def rob(self , nums: List[int]) -> int:
        # write code here
        n = len(nums)
        if n == 1:
            return nums[0]
        a = nums[0]
        b = max(nums[0], nums[1])
        for i in range(2, n):
            tmp = b
            b = max(nums[i] + a, b)
            a = tmp
        return b;    
        
全部评论
该牛油正在参与牛客写题解薅羊毛的活动,牛币,周边,京东卡超多奖品放送,活动进入倒计时!快来捡漏啦https://www.nowcoder.com/discuss/888949?source_id=profile_create_nctrack&channel=-1
点赞 回复 分享
发布于 2022-04-27 12:07

相关推荐

2024-12-04 19:46
海南大学 Java
Asp1rin:太长了,写的太啰嗦,缩到一页纸最好。项目描述太多,简单的功能就别写了,而且亮点写的太口语化
点赞 评论 收藏
分享
2024-12-06 10:44
东北财经大学 运营
在拧螺丝的西红柿很热情:工作量数据化,你的实习我只看到了一个30%,比如总浏览量十万加,同比增长20%,用户复购率达到70%等等,自己根据你当时的工作情况挖掘吧
点赞 评论 收藏
分享
评论
点赞
收藏
分享
牛客网
牛客企业服务