题目描述

LeetCode 第 198 题——打家劫舍（House Robber）

你是一个职业小偷，计划偷窃沿街的房屋。每间房内都藏有一定的现金，这个地方所有的房屋都围成一圈，并且相邻的房屋有安全系统会相连，如果两间相邻的房屋在同一晚上被打劫，系统会自动报警。

给定一个代表每个房屋存放金额的非负整数数组，计算你 在不触动警报装置的情况下，能够偷窃到的最高金额。

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

解题思路

这道题可以看作是一个斐波那契数列问题。因为要到达第 n 阶楼梯的方法数量等于到达第 n-1 阶楼梯和到达第 n-2 阶楼梯的方法数量之和。
具体来说：
到达第 n 阶楼梯的方法 = 到达第 n-1 阶楼梯的方法 + 到达第 n-2 阶楼梯的方法。
当 n=1 时，只有一种方法。
当 n=2 时，有两种方法。
因此，我们可以用动态规划来解决这个问题，使用一个数组或两个变量来存储到达每一阶楼梯的方法数量。

解题步骤

1.判断 n 是否小于或等于 2，如果是，直接返回 n。
2.初始化两个变量 a 和 b 分别代表到达 n-2 和 n-1 阶楼梯的方法数量，并设定初始值为 1 和 2。
3.从 3 开始遍历到 n，每一步更新 a 和 b 的值，b 的新值为 a 和 b 之和，而 a 的新值为原先 b 的值。
4.返回 b 的值，即为最终的答案。

具体步骤

1.如果房屋数量为 0，直接返回 0。
2.如果房屋数量为 1，直接返回该房屋的金额。
3.初始化一个长度为 n 的数组 dp，其中 dp[i] 表示到达第 i 间房屋时能够偷窃到的最高金额。
4.dp[0] 初始化为第一个房屋的金额，dp[1] 初始化为 max(nums[0], nums[1])，表示前两个房屋中金额较大者。
5.从第 2 间房屋开始，通过递推公式 dp[i] = max(dp[i-1], dp[i-2] + nums[i]) 计算出每间房屋能够偷窃到的最高金额。
6.返回 dp[n-1] 作为最终结果，即为到达最后一个房屋时能够偷窃到的最高金额。

代码实现

func rob(nums []int) int {
	n := len(nums)
   // 如果房屋数量为 0，直接返回 0
	if n == 0 {
		return 0
	}
   // 如果房屋数量为 1，直接返回该房屋的金额
	if n == 1 {
		return nums[0]
	}
	// 初始化动态规划数组 dp
	dp := make([]int, n)
	dp[0] = nums[0]
	dp[1] = max(nums[0], nums[1])
     // 初始化第一个房屋和前两个房屋的最大偷窃金额
	for i := 2; i < n; i++ {
		dp[i] = max(dp[i-1], dp[i-2]+nums[i])
	}
	// 返回最后一个房屋的最高偷窃金额
	return dp[n-1]
}

// max 函数返回两个整数中的最大值
func max(a, b int) int {
	if a > b {
		return a
	}
	return b
}

代码测试

func main() {
	// 测试用例
	testCases := [][]int{
		{1, 2, 3, 1},
		{2, 7, 9, 3, 1},
		{2, 1, 1, 2},
		{5, 3, 4, 11, 2},
	}

	// 遍历测试用例并输出结果
	for _, nums := range testCases {
		fmt.Printf("房屋金额: %v, 最高偷窃金额: %d\n", nums, rob(nums))
	}
}

测试结果

关于题目疑问

Q1 dp[i] = max(dp[i-1], dp[i-2] + nums[i]) 这个递推公式是怎么算出来的

我们要解决的问题是：在一排房屋中，小偷不能同时偷窃相邻的两间房屋，求能偷窃到的最大金额。
假设我们已经计算到了第 i 间房屋，面临两个选择：
不偷第 i 间房屋：那么小偷能获得的最大金额就是前一间房屋的最大偷窃金额，即 dp[i-1]。
偷第 i 间房屋：由于不能偷相邻的房屋，因此小偷只能选择从第 i-2 间房屋开始偷，这时的最大偷窃金额为 dp[i-2]，再加上第 i 间房屋的金额 nums[i]，总金额为 dp[i-2] + nums[i]。

递推公式推导：
基于上面的分析，我们可以得出：
如果小偷选择不偷第 i 间房屋，最大金额为 dp[i-1]。
如果小偷选择偷第 i 间房屋，最大金额为 dp[i-2] + nums[i]。
为了保证小偷获得的总金额最大，我们在这两种选择中取较大值
dp[i] = max(dp[i-1], dp[i-2] + nums[i])

总结

dp[i] 的值取决于是否选择偷窃当前的房屋 i，以及偷窃之前房屋的情况。
递推公式 dp[i] = max(dp[i-1], dp[i-2] + nums[i]) 就是基于这两种选择所能获得的最大金额计算出来的。
最终，dp[n-1] 就是小偷在 n 间房屋内所能获得的最大金额。

Q2 什么是动态规划？

动态规划（Dynamic Programming，简称 DP）是一种算法设计技巧，用于解决具有重叠子问题和最优子结构性质的问题。它的核心思想是通过将问题分解为更小的子问题，逐步求解并保存这些子问题的解，从而构建出原问题的解。动态规划通常用于优化问题，尤其是那些存在多种可能选择或路径的问题。

例子分析
举例来说，abb 和 egg 是同构的，因为可以通过如下映射来匹配：
a -> e
b -> g
这意味着字符串 s 中的每个字符都可以找到一个对应的字符 t，并且这个映射在整个字符串中是一致的。

动态规划核心思想

重叠子问题：
问题可以被分解为多个子问题，这些子问题之间存在重叠，也就是说，同一个子问题会被多次计算。
例如，在计算斐波那契数列时，F(n) = F(n-1) + F(n-2)，其中 F(n-1) 和 F(n-2) 是重复计算的子问题。
最优子结构：
一个问题的最优解可以通过其子问题的最优解组合而成。
例如，在最短路径问题中，找到从起点到终点的最短路径可以通过找到从起点到某个中间节点的最短路径，再加上从该中间节点到终点的最短路径来实现。
状态转移方程：
动态规划通过状态转移方程来表示问题的递推关系。这个方程通常是基于问题的最优子结构性质来构建的。
例如，在打家劫舍问题中，状态转移方程是 dp[i] = max(dp[i-1], dp[i-2] + nums[i])，表示到第 i 间房屋时的最大偷窃金额。
存储中间结果：
为了避免重复计算，动态规划会存储已经计算过的子问题的结果，通常使用数组或表来保存这些中间结果。
例如，在计算斐波那契数列时，可以用一个数组来存储每一个 F(n) 的值，避免重复计算。

动态规划步骤

1.定义状态：确定如何表示问题的子问题，通常使用一个数组或表格来表示不同状态。例如，在打家劫舍问题中，dp[i] 表示从第 0 到第 i 间房屋的最大偷窃金额。
2.构建状态转移方程：根据问题的最优子结构，确定如何从一个状态转移到另一个状态。例如，在打家劫舍问题中，状态转移方程为 dp[i] = max(dp[i-1], dp[i-2] + nums[i])。
3.初始化：为状态数组或表格设定初始值。例如，斐波那契数列中，F(0) 和 F(1) 需要被初始化为 0 和 1。
4.计算并填表：根据状态转移方程，从初始状态开始逐步计算出所有的状态。
5.输出结果：最后输出表格中保存的最终结果。

总结

动态规划是一种非常强大的算法设计方法，适用于解决优化类问题，特别是那些具有重叠子问题和最优子结构的场景。它通过逐步解决子问题并存储结果来避免重复计算，从而显著提高了效率。