哪里可以做免费网站,网站建设术语解释,南充市建设局官方网站,深圳市建设工程交易服题目
198. 打家劫舍 你是一个专业的小偷#xff0c;计划偷窃沿街的房屋。每间房内都藏有一定的现金#xff0c;影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统#xff0c;如果两间相邻的房屋在同一晚上被小偷闯入#xff0c;系统会自动报警。
给定一个代…题目
198. 打家劫舍 你是一个专业的小偷计划偷窃沿街的房屋。每间房内都藏有一定的现金影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统如果两间相邻的房屋在同一晚上被小偷闯入系统会自动报警。
给定一个代表每个房屋存放金额的非负整数数组计算你在不触动警报装置的情况下能够偷窃到的最高金额。
示例 1:
输入: [1,2,3,1] 输出: 4 解释: 偷窃 1 号房屋 (金额 1) 然后偷窃 3 号房屋 (金额 3)。 偷窃到的最高金额 1 3 4 。 示例 2:
输入: [2,7,9,3,1] 输出: 12 解释: 偷窃 1 号房屋 (金额 2), 偷窃 3 号房屋 (金额 9)接着偷窃 5 号房屋 (金额 1)。 偷窃到的最高金额 2 9 1 12 。
分析
设f(k)为从前k个房子能够找到最大的金额Ai为第i个房子的金额
n 1 f(1) A1 n 2 f(2) max(A1, A2) n 3 :
第三个加第一个房子金额1,2,3,4)不加保持金额最大(2,1,1,2)
得出动态方程 f(k) max(f(k-2) Ai, f(k-1))
代码 数组越界的处理 func rob(nums []int) int {dp : make([]int, len(nums)2)for i, key : range nums {dp[i2] max(dp[i1], dp[i] key)}return dp[len(dp)-1]
}func max(n, m int) int {if n m {return n} else {return m}
}这个版本的代码不太好没有用到动态规划的方程。 func rob(nums []int) int {curr : 0prev : 0for _, key : range nums {temp : currcurr max(prevkey, curr)prev temp}return curr
}func max(n, m int) int {if n m {return n} else {return m}
}
