算法沉淀 —— 动态规划篇（简单多状态dp问题上）

电玩女神 2024-04-06 15:50 88阅读 0赞

#### 算法沉淀 —— 动态规划篇（简单多状态dp问题上） ####

*  前言
 *  一、按摩师
 *  二、打家劫舍 II
 *  三、删除并获得点数
 *  四、粉刷房子

## 前言 ##

几乎所有的动态规划问题大致可分为以下5个步骤，后续所有问题分析都将基于此

*  1.、状态表示：通常状态表示分为以下两种，其中更是第一种为主。
    
     *  `以i为结尾`，dp\[i\] 表示什么，通常为代求问题（具体依题目而定）
     *  `以i为开始`，dp\[i\]表示什么，通常为代求问题（具体依题目而定）
 *  2、状态转移方程
    
     *  以上述的dp\[i\]意义为根据， 通过`最近一步来分析和划分问题`，由此来得到一个有关dp\[i\]的状态转移方程。
 *  3、dp表创建，初始化
    
     *  动态规划问题中，如果直接使用状态转移方程通常会伴随着`越界访问`等风险，所以一般需要初始化。而初始化最重要的两个注意事项便是：`保证后续结果正确，不受初始值影响；下标的映射关系`。
     *  而`初始化一般分为以下两种：`
        
         *  `直接初始化开头的几个值。`
         *  `一维空间大小+1，下标从1开始；二维增加一行/一列`。
 *  4、填dp表、填表顺序：根据状态转移方程来确定填表顺序。
 *  5、确定返回值

## 一、按摩师 ##

【题目链接】：[面试题 17.16. 按摩师][17.16.]  
【题目】：

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

【分析】：  
 我们定义dp\[i\]表示从\[0, 1\]按摩师能找到的最优预约集合。但我们发现第i个位置还可以细分为两种情况：i号预约、i号不预约。因此我们进一步分析定义f\[i\]表示从开始到i位置，并且i号预约的最优集合；g\[i\]表示从开始到i位置，并且i号不预约的最优集合。  
 其中 `f[i] = g[i - 1] + nums[i - 1]`、`g[i] = max(g[i - 1], f[i - 1])`。  
【代码编写】：

class Solution {
        
    public:
        int massage(vector<int>& nums) {
        
            int n = nums.size();
            vector<int> f(n + 1);//f[i]表示[1, i]之间， 并且i号预约的最优集合
            vector<int> g = f;//g[i]表示[1, i]之间，并且i号不预约的最优集合
            //填表
            for(int i = 1; i <= n; i++)
            {
        
                g[i] = max(g[i - 1], f[i - 1]);
                f[i] = g[i - 1] + nums[i - 1];
            }
            return max(f[n], g[n]);
        }
    };

## 二、打家劫舍 II ##

【题目链接】：[LCR 090. 打家劫舍 II][LCR 090. _ II]  
【题目】：

>  一个专业的小偷，计划偷窃一个环形街道上沿街的房屋，每间房内都藏有一定的现金。这个地方所有的房屋都 围成一圈 ，这意味着第一个房屋和最后一个房屋是紧挨着的。同时，相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警 。  
>  给定一个代表每个房屋存放金额的非负整数数组 nums ，请计算 在不触动警报装置的情况下 ，今晚能够偷窃到的最高金额。

【实例】：

> 输入：nums = \[2,3,2\]  
> 输出：3  
> 解释：你不能先偷窃 1 号房屋（金额 = 2），然后偷窃 3 号房屋（金额 = 2）, 因为他们是相邻的。

【分析】：  
 显然题目中所有房屋形成了一个类似于环形结构，比较棘手。所以我们可以以1号房屋是否被偷进行分类讨论，将环形结构蜕变成普通数组，首尾不影响。  
 分类情况：因为房屋不能连续被偷。所以：

1.  如果1号房屋不被偷，此时模型简化为偷\[2, n\]号房屋，首位不影响。
2.  如果1号房屋被偷，此时意味着2号和n号房屋一段不被偷，此时模型简化为偷\[3, n-1\]号房屋，首位不影响。最后结果假设1号房屋所偷金额即可。

上述两种情况统一为偷\[begin, end\]号的房屋，相邻房屋不能都被偷。此时我们可以定义dp\[i\]表示小偷在\[begin, i\]号房屋间所偷的最大金额。当我们发现i位置还可细分为偷以不透。所以我们继续细分情况，定义f\[i\]表示小偷在\[begin, i\]之间，且i号房屋被偷的最大金额；g\[i\]表示小偷在\[begin, i\]之间，且i号房屋不被偷的最大金额。  
 此时f\[i\]的最近一步时，i-1号房屋不被偷，i号房屋被偷的最大金额，所以发f\[i\]的状态转移方程为`f[i] = g[i-1] + nums[i-1]`;对于g\[i\]来说，此时有两种情况，i-1号房屋被偷和不被偷的最大金额，所以g\[i\]的状态转移方程为`g[i] = max(f[i - 1], g[i - 1]`。最后比较f\[n\],g\[n\]，返回最大值即可。

【代码编写】：

class Solution {
        
    public:
        int rob(vector<int>& nums) {
        
            int n = nums.size();
            return max(_rob(nums, 2, n), _rob(nums, 3, n - 1) + nums[0]);
        }
    
        int _rob(vector<int>& nums, int begin, int end)
        {
        
            int n = nums.size();
            vector<int> f(n + 1);//f[i]表示[begin, i]号房屋中，i号房屋偷，偷窃到的最高金额
            vector<int> g = f;//g[i]表示[begin, i]号房屋中，i号房屋不偷，偷窃到的最高金额
            for(int i = begin; i <= end; i++)
            {
        
                f[i] = g[i - 1] + nums[i - 1];
                g[i] = max(f[i - 1], g[i - 1]);
            }
            return max(f[end], g[end]);
        }
    };

## 三、删除并获得点数 ##

【题目链接】：[740. 删除并获得点数][740.]  
【题目】：

>  给你一个整数数组 nums ，你可以对它进行一些操作。  
> 每次操作中，选择任意一个 nums\[i\] ，删除它并获得 nums\[i\] 的点数。之后，你必须删除 所有 等于 nums\[i\] - 1 和 nums\[i\] + 1 的元素。  
>  开始你拥有 0 个点数。返回你能通过这些操作获得的最大点数。

【实例】：

> 输入：nums = \[2,2,3,3,3,4\]  
> 输出：9  
> 解释：  
> 删除 3 获得 3 个点数，接着要删除两个 2 和 4 。  
> 之后，再次删除 3 获得 3 个点数，再次删除 3 获得 3 个点数。  
> 总共获得 9 个点数。

【分析】：  
 我们可以向通过一个数组hash，将原数组中所有相同元素(假设为x)的值累加后(假设结果为sum)，存放到hash中（下标为x, hash\[x\] = sum）。  
 通过第一步，我们可以将原问题转化为：在hash数组中，相邻元素的值不能同时获取，求最终所获得的点数的最大值!  
 我们定义f\[i\]表示在\[0, i\]中获取点数，并且保证hash\[i\]的元素被获取，最终所能获得的最大点；g\[i\]表示在\[0, i\]中获取点数，并且保证hash\[i\]的元素不被获取，最终所能获得的最大点数。可得状态转移方程为：`f[i] = g[i - 1] + hash[i];`、`g[i] = max(f[i - 1], g[i - 1])`！  
 从左往右依次填dp表后，返回结果最大值！  
【代码编写】：

class Solution {
        
    public:
        int deleteAndEarn(vector<int>& nums) {
        
            const int N = 10001;
            int hash[N] = {
        0};
            for(auto x : nums)
                hash[x] += x;
            vector<int> f(N);//f[i]表示从[1, i],i位置对应点数被获得，所获得的最大点数
            vector<int> g = f;//g[i]表示从[1, i],i位置对应点数不被获得，所获得的最大点数
            for(int i = 1; i < N; i++)
            {
        
                f[i] = g[i - 1] + hash[i];
                g[i] = max(f[i - 1], g[i - 1]);
            }
            return max(f[N - 1],g[N - 1]); 
        }
    };

## 四、粉刷房子 ##

【题目链接】：[LCR 091. 粉刷房子][LCR 091.]  
【题目】：

>  假如有一排房子，共 n 个，每个房子可以被粉刷成红色、蓝色或者绿色这三种颜色中的一种，你需要粉刷所有的房子并且使其相邻的两个房子颜色不能相同。  
>  当然，因为市场上不同颜色油漆的价格不同，所以房子粉刷成不同颜色的花费成本也是不同的。每个房子粉刷成不同颜色的花费是以一个 n x 3 的正整数矩阵 costs 来表示的。  
>  例如，costs\[0\]\[0\] 表示第 0 号房子粉刷成红色的成本花费；costs\[1\]\[2\] 表示第 1 号房子粉刷成绿色的花费，以此类推。  
>  请计算出粉刷完所有房子最少的花费成本。

【实例】：

> 输入: costs = \[\[17,2,17\],\[16,16,5\],\[14,3,19\]\]  
> 输出: 10  
> 解释: 将 0 号房子粉刷成蓝色，1 号房子粉刷成绿色，2 号房子粉刷成蓝色。  
> 最少花费: 2 + 5 + 3 = 10。

【分析】：  
 我们可以定义dp\[i\]表示粉刷\[0, i\]号房子，并且相邻房子颜色不同，其花费的最少成本。但我们发现i号防止可以细分为刷成红色、蓝色、绿色。

所以我们可以使用一个二维数组，其中dp\[i\]\[0\]表示粉刷\[0, i\]号房子，且i号房子为蓝色的最小花费；dp\[i\]\[1\]表示粉刷\[0, i\]号房子，且i号房子为绿色的最小花费；dp\[i\]\[0\]表示粉刷\[0, i\]号房子，且i号房子为红色的最小花费！！

显然状态转移方程为： `dp[i][0] = min(dp[i - 1][1], dp[i - 1][2]) + costs[i - 1][0]`、`dp[i][1] = min(dp[i - 1][0], dp[i - 1][2]) + costs[i - 1][1]`、`dp[i][2] = min(dp[i - 1][0], dp[i - 1][1]) + costs[i - 1][2];`

从左往右依次填表，最后比较dp\[n\]\[0\]、dp\[n\]\[1\]、dp\[n\]\[2\]的最小值即可！  
【代码编写】：

class Solution {
        
    public:
        int minCost(vector<vector<int>>& costs) {
        
            int n = costs.size();
            vector<vector<int>> dp(n+1, vector<int>(3));
            //dp[i][0]表示粉刷[0, i]号房子，且i号房子为蓝色的最小花费
            //dp[i][1]表示粉刷[0, i]号房子，且i号房子为绿色的最小花费
            //dp[i][2]表示粉刷[0, i]号房子，且i号房子为红色的最小花费
            for(int i = 1; i <= n; i++)
            {
        
                dp[i][0] = min(dp[i - 1][1], dp[i - 1][2]) + costs[i - 1][0];
                dp[i][1] = min(dp[i - 1][0], dp[i - 1][2]) + costs[i - 1][1];
                dp[i][2] = min(dp[i - 1][0], dp[i - 1][1]) + costs[i - 1][2];
            }
            return min(dp[n][0], min(dp[n][1], dp[n][2]));
        }
    };

[17.16.]: https://leetcode.cn/problems/the-masseuse-lcci/description/
[LCR 090. _ II]: https://leetcode.cn/problems/PzWKhm/description/
[740.]: https://leetcode.cn/problems/delete-and-earn/description/
[LCR 091.]: https://leetcode.cn/problems/JEj789/description/