这一节我们讲解求线性规划问题的一般步骤：状态的定义和状态的转移。这里所说的一般步骤不是套路，而是求解这类问题必须要经历的两个步骤，线性规划的问题在算法问题中是比较具有艺术性的，一般而言没有固定的规律。
例1：LeetCode 第 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 。
分析：Robber 的意思是“盗贼，强盗”，这是我们做的第 3 个动态规划问题。
题目要求：你是一个专业的小偷，打算洗劫一条街的所有房子。每一个房子里都有不同价值的宝物，但是，如果你选择偷窃连续的两栋房子，就会触发报警系统。编程求出你最多可以偷窃价值多少的宝物？
如 ，则返回
；
如 ，则返回
。
分析题意，可以得到，这是一个最优化问题。如果没有好的解法，我们可以尝试使用暴力解法。偷取的房子只要不相邻，并且最终偷取的宝物的总价值最大就可以了。实际上，递归解法中实际上也蕴含了暴力求解的思想，只不过递归的暴力求解更智能，不会等到所有的可能解都求出来以后再判断，而是一边暴力一边判断。
暴力解法：检查所有房子的组合，对每一个组合，检查是否有相邻的房子，如果没有，记录其价值，找最大值。时间复杂度是 。
为了确定状态的定义和状态转移方程，我们可以画出这个问题的树形结构：
LeetCode 第 198 号问题：House Robber
我们对状态的定义：考虑偷取 范围里的房子 （函数的定义）即定义
为这条街上的第
个房子的价值，
为
这个范围里最多可以偷取的宝物的价值。则所求的解为
，则
可以表示成如下：
这个方程就是我们定义的状态转移的方程，这一步称之为，根据对状态的定义，决定状态的转移。
其中，含有递归定义的部分 就是所有的可能的组合。这是一个组合问题，所以我们可以按照一个顺序来找所有可能的组合。
分析题意，可以得到，这是一个最优化问题。如果没有好的解法，我们可以尝试使用暴力解法。偷取的房子只要不相邻，并且最终偷取的宝物的总价值最大就可以了。
在 个房子中选取几个房子的组合。对于这
个房子有
个组合，对于每一个组合中，有没有相邻的房子，如果有，应该去掉。没有相邻的房子，就可以计算总价值，记录，参与最后的比较
，暴力解法，耗时很多。
这个问题只要求我们求最大值。
我们分析这个问题的思路是：看看能不能使用递归的思考方式，在画出递归树的同时，观察这个问题是否出现了“重叠子问题”。并且，如果“重叠子问题”也是最优化问题，我们就可以使用“动态规划”来求解这个问题。
首先，分析出这是一个组合的问题，画出上面的图，发现，在递归树中存在重叠子问题，每一个问题都是一个最优化问题。满足（1）重叠子问题（2）最优子结构。所以可以用记忆化搜索和动态规划的方式来解决。
下面我们对这个问题给出一个形式化的分析：
每一个节点表示的一个要解决的问题，我们把它定义为状态，其实我们就可以把它理解为递归函数的函数的定义，这一点非常关键。所以我们建议，在编写代码的时候，把函数的定义写成注释，来提醒自己。
步骤：两个步骤，问问自己状态是什么？状态的转移是什么？
1、明确递归函数的定义（定义了状态，函数要做什么）；
2、根据对状态的定义，决定状态的转移（得到状态转移方程，函数要怎么做）；
状态是“递归函数定义的时候，对这个递归函数的定义”。这里的“考虑偷取 x 到 n-1”，对于 x 索引的位置，我并不一定要偷取。
从那张图中就可以发现这个规律。
“状态”定义了我们的递归函数要做什么，而“状态转移”定义了我们的递归函数要怎么做。
这个问题的初始解法：
说明：这里还没有加入“记忆化搜索”的步骤。下面，我们加入记忆化搜索。其实就是三个步骤：
1、定义缓存
2、缓存初始化
3、第一次计算加入缓存
4、每次计算之前查一下缓存，看看之前是否计算过
记忆化搜索的步骤就完成了。
解法二：动态规划
下面，我们使用“动态规划”的思路，自底向上来解决这个问题。
先找到最基础的问题是啥？这里要小心 n - 1 >= 0，以及数组是否越界。通过规模较小的问题，一步一步得到了规模较大的问题的解。
当我们把这个问题分析清楚以后，使用动态规划就非常简单。最终的算法复杂度是 这个级别的。
总结：再次强调，“状态”的定义是非常重要的。下面我们可以重新定义状态和状态的转移。作为练习，再来一遍。
实践：使用递归解决 198（注意，提交到 LeetCode 上不能通过）
Java 代码：
/**
* 没有记忆化搜索的递归，提交到 LeetCode 上不能通过
* Submission Result: Time Limit Exceeded
* Created by liwei on 17/10/3.
*/
public class Solution {
public int rob(int[] nums) {
// 针对特殊情况应该首先考虑到
if (nums == null || nums.length == 0) {
return 0;
}
return getRob(nums, 0);
}
// 状态的定义：[i,...,n-1] 这个些个房屋中能够偷取的宝物总和的最大值
// 有最大，一般就有一个遍历的过程
private int getRob(int[] nums, int start) {
// 递归终止条件
if (start >= nums.length) {
return 0;
}
int max = -1;
int len = nums.length;
// i 应该从 start 这个位置开始！
for (int i = start; i < len; i++) {
max = Integer.max(max, nums[i] + getRob(nums, i + 2));
}
return max;
}
}
Java 代码：使用记忆化搜索
/**
* 加入了记忆化搜索的递归
* Created by liwei on 17/10/3.
*/
public class Solution2 {
private int[] memory;
public int rob(int[] nums) {
int len = nums.length;
memory = new int[len + 1];
for (int i = 0; i < len + 1; i++) {
memory[i] = -1;
}
return getRob(nums, 0);
}
// 状态的定义：[i,...,n-1] 这个些个房屋中能够偷取的宝物总和的最大值
// 有最大，一般就有一个遍历的过程
private int getRob(int[] nums, int start) {
int max = -1;
int len = nums.length;
if (start >= nums.length) {
return 0;
}
if (memory[start] == -1) {
for (int i = start; i < len; i++) {
max = Integer.max(max, nums[i] + getRob(nums, i + 2));
}
memory[start] = max;
}
return memory[start];
}
}
Java 代码：使用动态规划
/**
* 使用动态规划解决
* Created by liwei on 17/10/3.
*/
public class Solution3 {
public int rob(int[] nums) {
if (nums == null) {
return 0;
}
int len = nums.length;
if (len == 0) {
return 0;
}
int[] memory = new int[len];
for (int i = 0; i < len; i++) {
memory[i] = -1;
}
for (int i = len - 1; i >= 0; i--) {
int max = -1;
for (int j = i; j < len; j++) {
max = Integer.max(max, nums[j] + (j + 2 >= len ? 0 : memory[j + 2]));
}
memory[i] = max;
}
return memory[0];
}
}
时间复杂度分析，对状态的定义：考虑偷取 [x…n-1] 范围里的房子 （函数的定义）。接下来，我们改变对状态的定义，将状态的定义修改成：考虑偷取 范围里的房子，其实就不用考虑边界问题了，因为边界问题，在前面的特殊情况中已经讨论过了。
Python 代码：
class Solution:
def rob(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
n = len(nums)
if n == 0:
return 0
dp = [-1] * n
# 前面这 4 行都是特判
if n <= 2:
return max(nums)
dp[0] = nums[0]
dp[1] = max(nums[0], nums[1])
# 状态的定义 dp[i]，考虑 [0,i] （包括物品 i 在内），能够偷取的物品的最大价值
for i in range(2, n):
# num[i] 偷和不偷，在这两种情况中选择一种
dp[i] = max(nums[i] + dp[i - 2], dp[i - 1])
return dp[-1]
练习
练习1：使用新的状态定义，完成问题
说明：其实上面的写法有点让人费解了。比较简单的做法就是从头到尾遍历。当前遍历的房子只有偷和不偷两种情况。
参考资料：https://blog.csdn.net/Koala_Tree/article/details/80015066
说明：该博主还有《剑指 Offer》和吴恩达深度学习课程笔记。
练习2：LeetCode 第 213 题：House Robber II
传送门：213. 打家劫舍 II。
你是一个专业的小偷，计划偷窃沿街的房屋，每间房内都藏有一定的现金。这个地方所有的房屋都围成一圈，这意味着第一个房屋和最后一个房屋是紧挨着的。同时，相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。
给定一个代表每个房屋存放金额的非负整数数组，计算你在不触动警报装置的情况下，能够偷窃到的最高金额。
示例 1:
输入: [2,3,2] 输出: 3 解释: 你不能先偷窃 1 号房屋（金额 = 2），然后偷窃 3 号房屋（金额 = 2）, 因为他们是相邻的。示例 2:
输入: [1,2,3,1] 输出: 4 解释: 你可以先偷窃 1 号房屋（金额 = 1），然后偷窃 3 号房屋（金额 = 3）。 偷窃到的最高金额 = 1 + 3 = 4 。
分析：和 House Robber 一样，不过这次是在一个环形街道中。也就是说给定的数组中，最后一个元素和第一个元素为邻居。在不触碰警报的情况下，问能够窃取的财产的最大值是多少？
先把 198 题做一遍，然后在 198 题的基础上完成 213 题。可以利用 198 题的结论来求解。因为对于 个房间，编号为
到
，我们可以将整体分为两个子序列，分别计算
和
，选取其中的最大值。
Python 代码：
class Solution:
def __rob_helper(self, nums):
n = len(nums)
if n == 0:
return 0
if n <= 2:
return max(nums)
dp = [-1] * 2
dp[0] = nums[0]
dp[1] = max(nums[0], nums[1])
for i in range(2, n):
dp[i % 2] = max(nums[i] + dp[(i - 2) % 2], dp[(i - 1) % 2])
return dp[(n - 1) % 2]
def rob(self, nums):
l = len(nums)
if l == 0:
return 0
if l <= 3:
return max(nums)
res1 = self.__rob_helper(nums[:-1])
res2 = self.__rob_helper(nums[1:])
return max(res1, res2)
C++ 代码：
class Solution {
public:
int rob(vector<int>& nums) {
int n = nums.size();
if (n < 2) return n ? nums[0] : 0;
return max(robber(nums, 0, n - 2), robber(nums, 1, n - 1));
}
private:
int robber(vector<int>& nums, int l, int r) {
int pre = 0, cur = 0;
for (int i = l; i <= r; i++) {
int temp = max(pre + nums[i], cur);
pre = cur;
cur = temp;
}
return cur;
}
};
练习3：LeetCode 第 337 题 ：House Robber III
传送门：337. 打家劫舍 III。
在上次打劫完一条街道之后和一圈房屋后，小偷又发现了一个新的可行窃的地区。这个地区只有一个入口，我们称之为“根”。 除了“根”之外，每栋房子有且只有一个“父“房子与之相连。一番侦察之后，聪明的小偷意识到“这个地方的所有房屋的排列类似于一棵二叉树”。 如果两个直接相连的房子在同一天晚上被打劫，房屋将自动报警。
计算在不触动警报的情况下，小偷一晚能够盗取的最高金额。
示例 1:
输入: [3,2,3,null,3,null,1] 3 / \ 2 3 \ \ 3 1 输出: 7 解释: 小偷一晚能够盗取的最高金额 = 3 + 3 + 1 = 7.示例 2:
输入: [3,4,5,1,3,null,1] 3 / \ 4 5 / \ \ 1 3 1 输出: 9 解释: 小偷一晚能够盗取的最高金额 = 4 + 5 = 9.
分析：和 House Robber 一样，不过这次是在一个小区中，整个小区成二叉树的结构。在不触碰警报的情况下，问能够窃取的财产的最大值是多少？我觉得这个问题主要考察了分类讨论。
Java 代码：
// 打家劫舍（三）：房子呈二叉树分布
class TreeNode {
int val;
TreeNode left;
TreeNode right;
TreeNode(int x) {
val = x;
}
}
public class Solution {
public int rob(TreeNode root) {
if (root == null) {
return 0;
}
int val = root.val;
if (root.left != null) {
val += rob(root.left.left) + rob(root.left.right);
}
if (root.right != null) {
val += rob(root.right.left) + rob(root.right.right);
}
return Math.max(val, rob(root.left) + rob(root.right));
}
}
练习4：LeetCode 第 309 题：Best Time to Buy and Sell Stock with Cooldown
传送门：309. 最佳买卖股票时机含冷冻期。
给定一个整数数组，其中第 i 个元素代表了第 i 天的股票价格 。
设计一个算法计算出最大利润。在满足以下约束条件下，你可以尽可能地完成更多的交易（多次买卖一支股票）:
- 你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。
- 卖出股票后，你无法在第二天买入股票 (即冷冻期为 1 天)。
示例:
输入: [1,2,3,0,2] 输出: 3 解释: 对应的交易状态为: [买入, 卖出, 冷冻期, 买入, 卖出]
（本节完）
网友评论