发表于 2024.10.07

• 这两道题目是LeetCode上的经典动态规划题目，都是关于打家劫舍的问题。对于第一道题目，可以定义一个数组dp，其中dp[i]表示在前i个房子中能偷到的最大金额。对于第i个房子，有两种选择：偷或者不偷。如果偷第i个房子，那么第i - 1个房子就不能偷，因此最大金额为dp[i - 2] + nums[i]；如果不偷第i个房子，那么最大金额取决于前i - 1个房子的结果，即dp[i - 1]。因此，状态转移方程为dp[i] = max(dp[i - 1], dp[i - 2] + nums[i])。最后，返回dp[n - 1]和dp[n - 2]中的较大值即可。

  而对于第二道题目，由于房子是环形的，因此可以分两种情况讨论：偷第一个房子和不偷第一个房子。对于第一种情况，dp[0] = nums[0]，第1到第n - 2个房子的偷法采用第一题的做法，而最后一个房子不能偷，即dp[n - 1] = dp[n - 2]；对于第二种情况，第一个房子不能偷，即dp[0] = 0，第1到第n - 1个房子的偷法采用第一题的做法，而最后一个房子可以偷，即dp[n - 1] = dp[n - 2]。最后，返回这两种情况的较大值即可。

  打家劫舍I的做法：

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

  打家劫舍II的做法：

  class Solution {
  public:
      int solve(vector<int> nums, bool first_selected) {
          // 如果`first_selected`为`true`，则第一个房子可以偷，但最后一个房子不能偷
          // 否则，第一个房子不能偷，最后一个房子可以偷
          // 其余的房子的偷法采用第一题的做法
  
          if (!first_selected) nums[0] = 0;
  
          if (nums.size() == 1) return nums[0];
  
          for (int i = 1; i < nums.size(); ++i) {
              if (i < nums.size() - 1 || !first_selected)
                  nums[i] = max(nums[i - 1], (i > 1 ? nums[i - 2] : 0) + nums[i]);
              else // i == nums.size() - 1 && first_selected
                  nums[i] = nums[i - 1];
          }
          return max(nums[nums.size() - 1], nums[nums.size() - 2]);
      }
  
      int rob(vector<int>& nums) {
          return max(solve(nums, true), solve(nums, false));
      }
  };

• LC 题目链接