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

共以下 1 个回答

• 塔底的仰望 永久会员 2023年9月16日 上午9:46

  dp[i]的定义为在第i个屋子，所能偷取的最大钱数
  时间复杂度O(n);空间复杂度O(1)

  class Solution {
      public int rob(int[] nums) {
          if (nums.length <= 1) {
              return nums[0];
          }
          int[] dp = new int[nums.length];
          //初始化
          boolean stealed = true;
          dp[0] = nums[0];
          dp[1] = nums[1];
          if (nums[0] > nums[1]) {
              dp[1] = dp[0];
              stealed = false;
          } // 1 2 4
          for (int i = 2; i < nums.length; i++) {
              if(stealed == false) {
                  dp[i] = dp[i - 1] + nums[i];
                  stealed = true;
              } else {
                  if (dp[i - 2] + nums[i] > dp[i - 1]) {
                      dp[i] = dp[i - 2] + nums[i];
                      stealed = true;
                  } else {
                      dp[i] = dp[i - 1];
                      stealed = false;
                  }
              }
          }
          return dp[nums.length - 1];
      }
  }
  

  0 赞同 0 条回复

  登录以回复