算法分析课程博客分享 9
746. 使用最小花费爬楼梯(Min Cost Climbing Stairs)
数组的每个索引做为一个阶梯，第 i个阶梯对应着一个非负数的体力花费值 cost[i](索引从0开始)。
每当你爬上一个阶梯你都要花费对应的体力花费值，然后你可以选择继续爬一个阶梯或者爬两个阶梯。
您需要找到达到楼层顶部的最低花费。在开始时，你可以选择从索引为 0 或 1 的元素作为初始阶梯。
示例 1:
输入: cost = [10, 15, 20]
输出: 15
解释: 最低花费是从cost[1]开始，然后走两步即可到阶梯顶，一共花费15。
示例 2: 输入: cost = [1, 100, 1, 1, 1, 100, 1, 1, 100, 1]
输出: 6
解释: 最低花费方式是从cost[0]开始，逐个经过那些1，跳过cost[3]，一共花费6。
注意：
- cost 的长度将会在 [2, 1000]。
- 每一个 cost[i] 将会是一个Integer类型，范围为 [0, 999]。
解题思路:
这星期实在忙得不行，所以只能选择一些比较简单的题目。爬楼梯问题属于比较经典的动态规划问题，考虑到我们单次可以选择爬一级阶梯或者两级阶梯，且爬第 n 级阶梯的花费为 cost [n]，假设我们爬到第 n 级阶梯的最低花费是 dp[n]，且我们已知爬到第 1 级至爬到第 n-1 级的最低花费。那么，爬到第 n 级的最低花费为 min(dp[n-2], dp[n-1]) + cost[n]。在获得状态转移方程的情况下，我们只要对 dp 数组进行初始化即可，显然，dp[0] = cost[0] 且 dp[1] = cost[1]。综上，我们需要返回的是 dp[-1] 与 dp[-2] 间的较小值，因为我们可以从这两级通过一次攀爬到达楼梯顶部，具体代码如下：
int minCostClimbingStairs(vector<int>& cost) {
vector<int> dp(cost.size(), INT_MAX);
dp[0] = cost[0];
dp[1] = cost[1];
for (int i = 2; i < dp.size(); ++i) {
dp[i] = min(dp[i-2], dp[i-1]) + cost[i];
}
return min(dp[dp.size()-2], dp[dp.size()-1]);
}
198. 打家劫舍(House Robber)
你是一个专业的小偷，计划偷窃沿街的房屋。每间房内都藏有一定的现金，影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。
给定一个代表每个房屋存放金额的非负整数数组，计算你在不触动警报装置的情况下，能够偷窃到的最高金额。
示例 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 。
解题思路:
这也是一道简单题，假设从第 n 间房间可以偷到的金额为 nums[n]，从第 1 间房间到第 n 间房间能偷到的最大金额为 dp[n]，在我们已知从第 1 间房间到第 n-1 间房间能偷到的最大金额的情况下，dp[n] = max(dp[i-1], dp[i-2]+nums[i])。具体为，我们不偷第 n 家房间时，从开始到第 n 间房能偷到的最大金额即 dp[n-1]；若我们打算偷第 n 间房间，那么我们从开始到第 n 间房能偷到的最大金额为从开始偷到第 n-2 间房能偷到的最大金额加上在第 n 间房可以偷到的金额，即 dp[i-2]+nums[i]。我们只需去上述两种情况的较大值作为 dp[n] 即可获得状态转移方程。我们还需要留意题目的一些陷阱，我们需要排除掉房间数目小于等于 2 的情况 (数目为 0 时，能偷到的金额为 0；数目为 1 时，能偷到的金额为 nums[0]；数目为 2 时，能偷到的金额为 max(nums[0], nums[1]))，具体代码如下：
int rob(vector<int>& nums) {
if (nums.empty())
return 0;
if (nums.size() == 1)
return nums[0];
vector<int> dp(nums.size(), 0);
dp[0] = nums[0];
dp[1] = max(dp[0], nums[1]);
for (int i = 2; i < dp.size(); ++i) {
dp[i] = max(dp[i-1], dp[i-2]+nums[i]);
}
return dp.back();
}
213. 打家劫舍 II(House Robber II)
你是一个专业的小偷，计划偷窃沿街的房屋，每间房内都藏有一定的现金。这个地方所有的房屋都围成一圈，这意味着第一个房屋和最后一个房屋是紧挨着的。同时，相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。
给定一个代表每个房屋存放金额的非负整数数组，计算你在不触动警报装置的情况下，能够偷窃到的最高金额。
示例 1:
输入: [2,3,2]
输出: 3
解释: 你不能先偷窃 1 号房屋（金额 = 2），然后偷窃 3 号房屋（金额 = 2）, 因为他们是相邻的。
示例 2:
输入: [1,2,3,1]
输出: 4
解释: 你可以先偷窃 1 号房屋（金额 = 1），然后偷窃 3 号房屋（金额 = 3）。偷窃到的最高金额 = 1 + 3 = 4 。
解题思路:
这道题在本质上和上一道题是一样的，唯一不同的地方在于此时的房间围成了一圈。我们要考虑这个变化会对我们的动态规划产生什么影响，显然，如果我们选择了偷第一间房间，我们则无法偷盗第 n 间房间。那么，我们可以偷到的房屋的范围实则是 1 ～ n-1 或者是 2 ～ n。因此，我们只需要在两个范围内分别进行动态规划，然后取较大的结果返回即可，具体代码如下：
int rob(vector<int>& nums) {
if (nums.empty())
return 0;
int size = nums.size();
if (size == 1)
return nums[0];
vector<int> dp1(size, 0), dp2(size, 0);
dp1[1] = nums[0];
dp2[1] = nums[1];
for (int i = 1; i < size-1; ++i) {
dp1[i+1] = max(dp1[i], dp1[i-1]+nums[i]);
dp2[i+1] = max(dp2[i], dp2[i-1]+nums[i+1]);
}
return max(dp1[size-1], dp2[size-1]);
}