动态规划课堂3-----简单多状态问题（买卖股票最佳时机）

���录

引入：

例题1：按摩师（打家劫舍I）

例题2：打家劫舍II

例题3：删除并获得点数

例题4：粉刷房子

例题5：买卖股票的最佳时机含冷冻

结语：

---

引入：

相信看到这里的友友们对动态规划已经有了一定的了解，下面我将介绍动态规划的简单多状态dp问题。所谓多状态就是在一步下有不同的情况要区分（例如买股票，今天可以分为买还是不买的多两种情况）。由于算法只讲知识点是远远不够的故下面我会在例题中穿插知识点帮助理解。动态规划一般的解题步骤还是1. 状态表示，2.状态转移方程，3.初始化，4.填表顺序，5.返回值。在写代码时一定要把这5步考虑清楚再写代码。

例题1：按摩师（打家劫舍I）

链接：按摩师

题目简介：

一个有名的按摩师会收到源源不断的预约请求，每个预约都可以选择接或不接。在每次预约服务之间要有休息时间，因此她不能接受相邻的预约。给定一个预约请求序列，替按摩师找到最优的预约集合（总预约时间最长），返回总的分钟数。

解法（动态规划）：

1. 状态表示：

对于简单的线性dp ，我们可以用「经验+题⽬要求」来定义状态表示例如：

（1）以某个位置为结尾的最小花费。

（2）以某个位置为起点到终点的最小花费。

故我们这题采用常用的方式：dp[i] 表⽰：选择到i 位置时，此时的最⻓预约时⻓。由于我们这个题在i 位置的时候，会⾯临选择或者不选择两种抉择，所依赖的状态需要细分。

下面之所以用f和g是因为高中我们所学的f（x）和g（x），可以换成其他的（但最好用f和g就当作是不成文的规定，这样代码的可读性会更高）。

（1）f[i] 表示：选择到i 位置时， nums[i] 必选，此时的最⻓预约时⻓。

（2）g[i]表示：选择到i 位置时， nums[i] 不选，此时的最⻓预约时⻓。

2.状态转移方程

因为状态表示定义了两个，因此我们的状态转移⽅程也要分析两个：

对于f[i] ：

如果nums[i] 必选，那么我们仅需知道i - 1 位置在不选的情况下的最⻓预约时⻓， 然后加上nums[i] 即可，因此f[i] = g[i - 1] + nums[i] 。

对于g[i] ：

如果nums[i] 不选，那么i - 1 位置上选或者不选都可以。因此，我们需要知道i - 1 位置上选或者不选两种情况下的最⻓时⻓，因此g[i] = max(f[i - 1], g[i - 1]) 。

在状态转移方程这里可以画图来帮助我们理解

3.初始化

这道题的初始化⽐较简单，因此⽆需加辅助节点（前两篇文章已解释），仅需初始化f[0] = nums[0], g[0] = 0 即可。

4.填表顺序

根据「状态转移⽅程」得「从左往右，两个表⼀起填」。

5.返回值

根据「状态表示」，应该返回max(f[n - 1], g[n - 1]) 。

代码实现如下：

class Solution {    public int massage(int[] nums) {        //1.创建dp表        //2.初始化        //3.填表        //4.返回值        int n = nums.length;        if(n == 0){            return 0;        }        int[] f = new int[n];//选择        int[] g = new int[n];//不选择        f[0] = nums[0];        for(int i = 1;i  
时间复杂度：O（n）
 
空间复杂度：O（n）
 
例题2：打家劫舍II
 
链接：打家劫舍II
 
题目简介：
 
你是一个专业的小偷，计划偷窃沿街的房屋，每间房内都藏有一定的现金。这个地方所有的房屋都 围成一圈 ，这意味着第一个房屋和最后一个房屋是紧挨着的。同时，相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警 。
 
给定一个代表每个房屋存放金额的非负整数数组，计算你 在不触动警报装置的情况下 ，今晚能够偷窃到的最高金额。
 
 解法（动态规划）：
 
通过阅读题目友友可以发现这题和例题一是差不多的，唯一不同就是例题二加了一个末尾和开头的限制。上⼀个问题是⼀个「单排」的模式，这⼀个问题是⼀个「环形」的模式，也就是⾸尾是相连的。但是我们可以将「环形」问题转化为「两个单排」问题：
 
（1）偷第⼀个房屋时的最大⾦额x ，此时不能偷最后⼀个房⼦，因此就是偷[0, n - 2] 区间的房⼦。
 
（2）不偷第⼀个房屋时的最大⾦额y ，此时可以偷最后⼀个房⼦，因此就是偷[1, n - 1] 区 间的房⼦。
 
两种情况下的「最大值」，就是最终的结果。
  
代码如下：
 
下面的rob1方法就是例题一。
 
class Solution {    public int rob(int[] nums) {        int n = nums.length;        return Math.max(nums[0] + rob1(nums,2,n - 2), rob1(nums,1,n - 1));    }    public int rob1(int[] nums,int left,int right){        if(left > right){            return 0;        }        //1.创建dp表        //2.初始化        //3.填表        //4.返回值        int n = nums.length;        int[] f = new int[n];        int[] g = new int[n];        f[left] = nums[left];        for(int i = left + 1;i