LeetCode 198.打家劫舍

Racket

解法2：动态规划

(define/contract (rob nums)
  (-> (listof exact-integer?) exact-integer?)
  (let ((n (length nums)))
    ;; 处理边界情况
    ;; 如果房子的数量 n 是0或1,函数返回0(没有房子可抢)
    ;; 或第一个房子的金额(只有一个房子时)。
    (if (<= n 1)
        (if (= n 0) 0 (car nums))
        ;; 正式开抢
        ;; 使用向量 dp 来存储每个房子的最大抢劫金额。
        ;; 长度是 n + 1,并且所有元素都初始化为0。
        (let ((dp (make-vector (+ n 1) 0)))
          ;; 第一个房子的最大可抢金额就是它本身的金额
          (vector-set! dp 1 (car nums))
          ;; 从第2个房子开始,每个房子都有两个选择:抢劫或跳过。
          ;; 如果抢劫,我们就取前面一个房子的最大值加上当前房子的金额。
          ;; 如果跳过,我们就取前两个房子的最大值。
          ;; 这两种策略中的最大值就是当前房子的最大抢劫金额。
          (for ([i (in-range 2 (+ n 1))])
            (vector-set! dp i (max (vector-ref dp (- i 1))
                                   (+ (vector-ref dp (- i 2))
                                      (list-ref nums (- i 1))))))
          ;; 在所有的房子都被考虑过后,最后一个元素 dp[n]
          ;; 包含了最大的抢劫金额,因此这是我们的返回值。
          (vector-ref dp n))))
  )

Q1

Q：在这段代码中，我有一个疑问：我们是从头开始遍历，根据每个房子抢与不抢来判断从头至此的最大值，假设后面还有一个金额很高的大房子，我们会不会因为当下的局部最优，结果导致后面真正遇到大房子时，没抢到大房子，最终导致“捡了芝麻，丢了西瓜”？

A：您的疑问很好。在解决此问题时，动态规划确实考虑了这种情况，并通过计算局部和全局的最优解来确保最终得到的是全局的最优解。

关键在于这里的状态转移方程。考虑任意一个房子i，我们有两个选择：抢劫或不抢劫。

如果我们选择抢劫房子i，那么我们不能抢劫房子i-1。因此，我们选择的是dp[i-2] + nums[i]（这里的dp[i-2]表示在房子i-2之前可以抢劫的最大金额，加上当前房子i的金额）。
如果我们选择不抢劫房子i，那么我们的最大金额就是dp[i-1]，这意味着我们抢劫了房子i-1或选择跳过了房子i-1，但不管怎样，dp[i-1]都是房子i-1之前可以获得的最大金额。

每一步，我们都会选择上述两个选项中的最大值作为dp[i]的值。这样，我们确保了在每一步都会考虑全局的最优选择，而不仅仅是基于当前房子的局部最优选择。

因此，尽管我们确实是从头开始遍历的，但由于我们在每一步都考虑了所有的可能性，我们可以确信最后得到的答案是全局最优解。

此外，这种算法确保了即使在列表的最后有一个金额很高的房子，我们也不会因为早期的局部最优选择而错过它。因为如果抢劫那个大房子是最优的选择，那么dp数组会正确地捕获这一点。

Q2

Q：在最初审题的时候，如何才能想到这一点？我总是担心怕漏掉后面的大房子，而不知道这是一个动态规划问题。

A：识别问题是否可以使用动态规划（Dynamic Programming, DP）通常依赖于对问题的深入理解和经验。以下是一些建议和策略，帮助您在面对此类问题时，更容易地识别并应用动态规划：

存在重叠子问题：如果问题可以分解为较小的子问题，并且这些子问题的解决方案在解决整个问题时被多次使用，那么这可能是一个DP问题。
最优子结构：问题的全局最优解可以从其子问题的最优解推导出来。
试着考虑简单的情况：首先考虑最简单的情况，例如一个只有1或2个房子的列表。然后逐渐增加复杂性，并尝试找出一个模式或递归关系。
画出解决方案的决策树：决策树可以帮助您可视化每一步的选择。如果您注意到树中有很多重复的部分，这可能意味着存在重叠的子问题，动态规划可能是一个好的方法。
使用表格法思考：试着使用表格记录中间结果。例如，在“打家劫舍”问题中，您可以为每个房子创建一个列表或数组，并考虑如果只有这些房子时，您能够抢劫的最大金额是多少。
不必担心先验知识：许多经典的动态规划问题，例如背包问题、最长公共子序列等，都有其特定的模式。熟悉这些问题和它们的解决方案可以帮助您更好地识别和解决新的动态规划问题。

对于您的担忧——怕漏掉后面的大房子，这其实是动态规划所试图解决的核心问题之一：如何确保我们不会因为局部最优而错过全局最优。在动态规划中，我们并不是基于任何一种预见性或关于后续房屋的知识来做决策，而是基于当前和之前的知识来做出最佳的决策。每一步的决策都考虑了所有的可能性，从而确保我们得到的是全局最优解。

最后，正如任何其他技能一样，识别和应用动态规划需要时间和练习。随着您解决越来越多的问题，您会变得越来越熟练。

解法1：超出内存限制

(define (robbing nums index history)
  ; (displayln history)
  (cond
    ((null? nums) (apply max (map car history)))
    (else
     (robbing
      (cdr nums) 
      (add1 index)
      (foldr (lambda (item acc)
               (append (cond
                         ((= (add1 (cadr item)) index) (list item)) ;;打不了
                             (else (list (list (+ (car item) (car nums)) index) ;;打
                                         item))) ;;不打
                         acc)) 
             '() history)))))

(define/contract (rob nums)
  (-> (listof exact-integer?) exact-integer?)
  (robbing (cdr nums) 1 (list (list (car nums) 0) (list 0 -1)))
  )

本文作者：Maeiee

本文链接：LeetCode 198.打家劫舍

版权声明：如无特别声明，本文即为原创文章，版权归 Maeiee 所有，未经允许不得转载！

喜欢我文章的朋友请随缘打赏，鼓励我创作更多更好的作品！