解题步骤

  1. 定义子问题：f(k) = max ( f(k-2) + ak , f(k-1) )
  2. 反复执行：从2循环到 n，执行上述公式

通过动态规划的方式实现

  • 时间复杂度：O (n)

  • 空间复杂度：O (n)

    1. function rob(nums) {
    2.   if (nums.length === 0) return 0;
    4.   const dp = [0, nums[0]];
    6.   for (let i = 2; i <= nums.length; i++) {
    7.       dp[i] = Math.max(dp[i - 2] + nums[i - 1], dp[i - 1]);
    8.   }
    10.   return dp[nums.length];
    11. }

代码中存在一个循环，所以时间复杂度是 O (n)。而空间复杂度也是 O (n)，因为使用了数组存储数据，数据会随着 n 增大而增大。

通过动态规划的方式实现（优化后）

  • 时间复杂度：O (n)

  • 空间复杂度：O (1)

    1. function rob(nums) {
    2.   if (nums.length === 0) return 0;
    4.   let dp0 = 0;
    5.   let dp1 = nums[0];
    7.   for (let i = 2; i <= nums.length; i++) {
    8.       const dp2 = Math.max(dp0 + nums[i - 1], dp1);
    10.       dp0 = dp1;
    11.       dp1 = dp2;
    12.   }
    14.   return dp1;
    15. }

代码中存在一个循环，所以时间复杂度是 O (n)。而空间复杂度是 O (1)，因为把数据存储的方式改成了单个变量的存储方式。