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

共以下 4 个回答

• 陆狗陆狗 普通 2025年1月2日 上午9:24

  解题思路
  – dp[i] 最大的金额
  – 如果i-1已经拿取，那么金额为dp[i]=dp[i-1]；如果i-1没有拿取（i-2可能也没拿，但是用dp[i-2]是没问题的），那么金额为dp[i]=dp[i-2]+nums[i]
  【题解1】常规的dp写法即可，关键是判断dp[i-1]和dp[i]的过渡关系

  class Solution {
      public int rob(int[] nums) {
          // dp[i] 最大的金额
          // 如果i-1已经拿取，那么金额为dp[i]=dp[i-1]；如果i-1没有拿取（i-2可能也没拿，但是用dp[i-2]是没问题的），那么金额为dp[i]=dp[i-2]+nums[i]
          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];
      }
  }
  

  0 赞同 0 条回复

  登录以回复
• Pendulumpal 普通 2024年12月25日 下午9:41

  只和前两个房屋相关

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

  0 赞同 0 条回复

  登录以回复
• Aatorx 永久会员 2024年12月25日 下午4:27

  class Solution {
  public:
      int rob(vector<int>& nums) {
          if(nums.size() == 1) {
              return nums[0];
          }
          int dp1 = nums[0];
          int dp2 = max(nums[0], nums[1]);
          for(int i = 2; i < nums.size(); i++) {
              int dp3 = max(dp2, dp1 + nums[i]);
              dp1 = dp2;
              dp2 = dp3;
          }
          return dp2;
      }
  };
  

  时间复杂度O(N)，空间复杂度O(1)。

  0 赞同 0 条回复

  登录以回复
• 秋山丽奈 普通 2024年12月24日 下午8:27

  思路： 递归

  class Solution {
  
  
      public int rob(int[] nums) {
  
          // // 使用 递归 
          // int[] remember = new int[nums.length];
          // for(int i = 0; i < remember.length; i ++){
          //     remember[i] = -1;
          // }
          // return dfs(nums, remember, nums.length-1);
  
          // 使用 递推 
          int f0 = 0;
          int f1 = nums[0];
  
          for(int i = 1; i <  nums.length; i ++){
              int newF = Math.max(f0+nums[i], f1);
              f0 = f1;
              f1 = newF;
          }
  
          return f1;
      }
  
  
      // 使用 递归解决 
      // 由于 未使用 记忆化 会导致 时间超时 
      public int dfs(int[] nums, int index){
  
          if(index < 0){
              return 0;
          }
          return Math.max(dfs(nums, index-1), dfs(nums, index-2)+nums[index]);
      }
  
      // 进行 记忆化 
      public int dfs(int[] nums, int[] remember, int index){
  
          if(index < 0){
              return 0;
          }
  
          if(remember[index] != -1){
              return remember[index];
          }else{
              int ans = Math.max(dfs(nums, index-1), dfs(nums, index-2)+nums[index]);
              remember[index] = ans;
              return ans;
          }
  
      }
  }
  

  0 赞同 0 条回复

  登录以回复