DP-House Robber

淡淡的烟草味﹌ 2022-07-14 03:29 25阅读 0赞

# House Robber #

[House Robber][]  
题目大意：  
一个小偷准备偷窃一条街道上的房屋，但这些房屋中任意相邻的房屋在同一夜被偷盗，那么就会自动报警。每个房屋中可偷盗的物品价值不一样，如果你是一名窃贼，怎么在同一夜中偷窃物品价值最大而不触发报警装置？

## 分析 ##

### 什么样的最优化问题适合使用DP ###

如何判断一个问题是否可用动态规划算法求解？

下面是引用《算法导论》中什么问题才能使用DP的论述：

> 《算法导论》中论述什么情况下可能适用动态规划？
> 
> 适合采用动态规划的方法的最优化问题的两个要素：最优子结构和重叠子问题。
> 
> 最优子结构  
> 用动态规划求解优化问题的第一步是描述最优解的结构。如果问题的一个最优解中包含了子问题的最优解，则该问题具有最优子结构。当一个问题**具有最优子结构**时，提示我们动态规划可能适用。（注意：在这种情况下，贪心策略可能也适用的）。
> 
> 重叠子问题  
> 适用于动态规划求解的最优化问题必须具有的第二个要素是子问题的空间要“很小”，也就是用来解原问题的递归算法可反复地解同样的子问题，而不是总在产生新的子问题。典型地，不同的子问题数是输入规模的一个多项式。当一个递归算法不断地调用同一个问题时，我们说该最有问题**包含重叠子问题**。相反地，适合用分治法解决的问题往往在递归的每一步都产生全新的问题。动态规划算法总是充分利用重叠子问题，即通过每个子问题只解一次，把解保存在一个在需要时就可以查看的表中，而每次查表得时间为常数。

DP的类型有：treeDP，背包，各种区间、网格、线性DP，状态压缩

### 关于House Robber ###

House Robber的问题可以抽象成一个非负整型数组，数组中的每一个整数都为每间房子中物品的价值。那么假设数组A=\[2, 3, 2, 1, 3, 2\]，按照**偷窃规则**：不能偷窃相邻的两间房子的物品，那么就是若取A\[0\]，那么就不能取A\[1\]，可以取A\[2\]。。。,因此确定取某元素时，其相邻位置的元素绝对不能取。结果是按照偷窃规则，小偷可以偷窃的最大价值是多少？

很明显这里求最大价值就是求最优化的问题。那么这个问题适合使用DP吗？  
能不能使用DP，看题目中是否存在符合使用DP的两个要素：1、是否具有最优子结构；2、是否包含重叠子问题。

#### 最优子结构 ####

按照规则求数组A=\[2, 3, 2, 1, 3, 2\]的最大值。那么可以用f(i)为数组A的最大值，f为指定规则的函数，i为数组的大小。  
根据不能取相邻元素的规则，f(i) 的结果是否包含数组中第i个元素，分两种情况：  
1）包含：那么f(i) = f(i-2) + A\[i-1\], f(i-2) + A\[i-1\] > f(i-1)  
2 ) 不包含：那么f(i) = f(i-1), f(i-1) > f(i-2) + A\[i-1\]  
总结：f(i) = max(f(i-1), f(i-2) + A\[i-1\])

因为求f(i)时，需要知道f(i-1)、f(i-2)，且f(i-1), f(i-2) 都是求相应数组大小的最大值，所以求f(i)也包含了求f(i-1)、f(i-2)，那么就符合了最优子结构的定义。

#### 重叠子问题 ####

由题意：  
当i = 0时，f(0) = 0，表示当数组为空时，数组最大值f(i)为0  
当i = 1时，f(1) = A\[0\],表示当数组只有一个元素时，数组最大值为A\[0\]  
当i = 2 时，f(2) = max(A\[0\], A\[1\]) = max(f(1), f(0) + A\[1\])，表示当数组有两个元素时，根据规则，数组最大值为max(A\[0\], A\[1\])  
当i = 3 时，f(3) = max(f(2), f(1) + A\[2\])  
。。。  
那么，求f(n) = max(f(n-1), f(n-2) + A\[n-1\]), 其中f(n-2)和f(n-1)都是f(n)的重叠子问题。

因此，House Robber是一个DP类型的题目

## DP求解 ##

int rob(vector<int>& nums) {
            int size = nums.size();
            if (size == 0)
                return 0;
            vector<int> sum(size+1, 0);
    
            sum[1] = nums[0];
            for (int i = 2; i <= size; i++) {
                sum[i] = max(sum[i-1], sum[i-2]+nums[i-1]);
            }
    
            return sum[size];  
        }

# 参考 #

算法导论

[House Robber]: https://leetcode.com/problems/house-robber/