【数据结构与算法】之“打家劫舍”的算法实现

一、题目要求

假设你是一个专业的小偷，计划偷窃沿街的房屋。每间房内都藏有一定的现金，影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。
给定一个代表每个房屋存放金额的非负整数数组，计算你不触动警报装置的情况下 ，一夜之内能够偷窃到的最高金额。

• 示例一

	输入：[1,2,3,1]
	输出：4
	解释：偷窃 1 号房屋 (金额 = 1) ，然后偷窃 3 号房屋 (金额 = 3)。
	     偷窃到的最高金额 = 1 + 3 = 4 。

  

 

  
1
  
2
  
3
  
4
 

• 示例二

	输入：[2,7,9,3,1]
	输出：12
	解释：偷窃 1 号房屋 (金额 = 2), 偷窃 3 号房屋 (金额 = 9)，接着偷窃 5 号房屋 (金额 = 1)。
	     偷窃到的最高金额 = 2 + 9 + 1 = 12 。

  

 

  
1
  
2
  
3
  
4
 

• 提示

	0 <= nums.length <= 100
	0 <= nums[i] <= 400

  

 

  
1
  
2
 

二、算法示例

• 思路：定义 dp 数组， dp[i] 表示从0 开始到 i 这个房子，能偷到的最大金额。
• 动态规划一：
  • 定义一个二维数组 dp[i][j] , 其中 i 表示截止到 i 这个房子， j 表示这个房子需不需要偷。
  • 于是 dp[i][0] 表示不偷这个房子的时候，所能得到的最大金额；dp[i][1] 表示需要偷这个房子的时候，说你得到的最大金额。
  • 如果不偷这个房子，我们需要计算 i-1 的时候，两种情况的最大金额。而偷这个房子的时候，我们只需要计算， i-1 时，不偷所能获得的最大金额，再加上当前房子的金额即可。
  • 在结尾的时候，我们只有可能是正好偷了倒数第二的房间或者倒数第一的房间。
• 动态规划一算法如下：

	func rob(_ nums: [Int]) -> Int {
      if nums.count == 0 {
        return 0
      }
    
      let n = nums.count
      var dp = [[Int]](repeating: [Int](repeating: 0, count: 2), count: n)
   
      dp[0][0] = 0
      dp[0][1] = nums[0]
    
      for i in 1..<n {
        dp[i][0] = max(dp[i-1][0], dp[i-1][1])
        dp[i][1] = dp[i-1][0] + nums[i]
      }
       return max(dp[n-1][0], dp[n-1][1])
    }

  

 

  
1
  
2
  
3
  
4
  
5
  
6
  
7
  
8
  
9
  
10
  
11
  
12
  
13
  
14
  
15
  
16
  
17
 

• 动态规划二：
  • 这个动态转移方程就有所不一样，我们定义 dp[i] 为 截止到 i 时，所能获得的最大金额。那么值应该是在 i-1 的时候，所能获得的最大金额，和 i-2 的时候，所能获得的最大金额加上当前金额，这二选一。
  • 对于转移方程 dp[i] = max(dp[i-2]+nums[i], dp[i-1])，这里并不知道 i-1 是偷了还是没偷；
  • 假如 i-1 没偷，那么我们可以知道 dp[i-1] = dp[i-2]，那么 dp[i] 应该等于 dp[i-2]+nums[i]；
  • 假如 i-1 偷了，那么 dp[i] = dp[i-1]，可以发现，我们再递推的时候，所有可能性都考虑到， 因此动态转移方程没有问题。
• 动态规划二算法如下：

	func rob(_ nums: [Int]) -> Int {
      if nums.count == 0 {
        return 0
      }
      if nums.count == 1 {
        return nums[0]
      }
    
      var dp = [Int](repeating: 0, count: nums.count)
      dp[0] = nums[0]
      dp[1] = max(dp[0], nums[1])
      var maxV = dp[1]

      for i in 2..<nums.count {
        dp[i] = max(dp[i-2]+nums[i], dp[i-1])
        maxV = max(maxV, dp[i])
      }
       return maxV
    }

  

 

  
1
  
2
  
3
  
4
  
5
  
6
  
7
  
8
  
9
  
10
  
11
  
12
  
13
  
14
  
15
  
16
  
17
  
18
  
19
 

• 动态规划三：
  • 定义 dp[i] 为房间角标 i 必抢的时候，所能偷到的最大金额，那么很容易得出：
    dp[i] = max(dp[i-2]+nums[i], dp[i-3]+nums[i])
  • 因为不能偷相邻的房间，所以要想偷 i 的房间的时候，我们可以考虑先得到 i-3 或者 i-2 的最大金额即可；
  • 至于为什么不考虑 i-5 或者 i-4，那是因为每一间房子金额都是正数，所以 i-3 必然是大于 i-5，i-2 必然大于 i-4。
• 动态规划三算法如下：

	func rob(_ nums: [Int]) -> Int {
      if nums.count == 0 {
        return 0
      }
      if nums.count == 1 {
        return nums[0]
      }
    
      if nums.count == 2 {
        return max(nums[0], nums[1])
      }
 
      //! 必偷的最大金额
      var dp = [Int](repeating: 0, count: nums.count)
      dp[0] = nums[0]
      dp[1] = nums[1]
      dp[2] = nums[0] + nums[2]
    
      for i in 3..<nums.count {
        dp[i] = max(dp[i-2]+nums[i], dp[i-3]+nums[i])
      }
   
      return max(dp[nums.count-1], dp[nums.count-2])
    }

  

 

  
1
  
2
  
3
  
4
  
5
  
6
  
7
  
8
  
9
  
10
  
11
  
12
  
13
  
14
  
15
  
16
  
17
  
18
  
19
  
20
  
21
  
22
  
23
  
24
 

文章来源: blog.csdn.net，作者：Serendipity·y，版权归原作者所有，如需转载，请联系作者。

原文链接：blog.csdn.net/Forever_wj/article/details/108675888