初级算法-动态规划-打家劫舍

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

摘一个示例做个说明.
示例 1：
输入：[1,2,3,1]
输出：4
解释：偷窃 1 号房屋 (金额 = 1) ，然后偷窃 3 号房屋 (金额 = 3)。
     偷窃到的最高金额 = 1 + 3 = 4 。

条件分析:

1. 如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警 -> 不能偷相邻两个房间的
2. 存放非负整数 -> 不用考虑减少的情况

解决思路1:

1. 根据分析1,说明每次都不能偷相邻房间
2. 根据分析2,可以确定偷肯定是增加的

采用二维数组进行存储.每次都存上当天偷和不透的总和.然后与前天不偷的数据进行对比,然后取最大值即可.如果前一天不偷,当天偷比前天偷当天不偷大,则偷,否则不偷.

func rob(_ nums: [Int]) -> Int {
    // 如果只有一天,则直接偷,然后返回第一天内容即为偷窃最高金额
    if nums.count == 1 {
        return nums[0]
    }
    let count = [Int](repeating: 2, count: nums.count)
    // 定义二维数组存储每天偷和不偷的偷窃金额
    var dp = [[Int]](repeating: count, count: nums.count)
    // 第一天不偷
    dp[0][0] = 0
    // 第一天偷
    dp[0][1] = nums[0]
    
    //循环存储
    for i in 1 ..< nums.count {
        // 当天不偷,前一天偷的最大值
        dp[i][0] = max(dp[i-1][0], dp[i-1][1])
        // 当天偷,前一天不偷
        dp[i][1] = nums[i] + dp[i - 1][0]
    }
    
    return max(dp[nums.count - 1][0], dp[nums.count - 1][1])
}

打家劫舍 提交结果.jpg

测试用例:

// 最小值
let nums = [0]
let nums = [1]
// 最大值
let nums = [400]
// 批量正常数据
let nums = [1,1,24,5,6,67,7]
let nums = [1,9,1,24,5,6,67,7]
let nums = [1,1,9,1,24,5,24,5,6,67,7]
let nums = [9,1,24,5,1,1,24,5,6,67,7]
let nums = [400,1,24,5,6,67,79,1,24,5,]

考察要点:

• 数组
• 动态规划