【动态规划 | 多状态问题】动态规划求解多状态问题

算法	相关知识点	可以通过点击	以下链接进行学习	一起加油！
斐波那契数列模型	路径问题

多状态问题通常涉及多个决策点和状态转换，解决起来复杂且计算量大。动态规划作为一种强大的算法工具，能够通过将问题分解为子问题并逐步求解，显著提升解决这类问题的效率。本文将探讨如何运用动态规划技术有效处理复杂的多状态问题，帮助读者理解其背后的原理，并展示如何设计高效的状态转移方程以优化问题求解过程。

🌈个人主页：是店小二呀
🌈C/C++专栏：C语言\ C++
🌈初/高阶数据结构专栏： 初阶数据结构\ 高阶数据结构
🌈Linux专栏： Linux
🌈算法专栏：算法
🌈Mysql专栏:Mysql

🌈你可知:无人扶我青云志 我自踏雪至山巅

面试题 17.16. 按摩师

【题目】：面试题 17.16. 按摩师

【算法思路】

通过题目分析，状态可以表示为选择到第 i 位置时的最长预约时长。进一步细化后，题目提供了两种状态：是否选择 nums[i]，这会影响最终结果。为此，我们可以创建两个 DP 表，分别表示选择或不选择 nums[i] 的情况，并根据不同状态进行处理。

题目要求不能连续选择，因此我们需要根据状态的定义以及与前一个状态之间的关系，推导出状态转移方程。对于不选择 nums[i] 的情况，上一状态的选择与否都会影响当前的最长预约时长，这与具体的选择策略密切相关

解决问题的关键在于，通过在第 i 位置引入多种状态，利用动态规划（DP）来求解。结合题目需求，我们需要确保DP表之间的状态连续性，从而推导出合理的状态转移方程。

【代码实现】

class Solution {
public:int massage(vector<int>& nums) {int n = nums.size();if(n == 0) return 0;///1.为多状态创建dp表vector<int> f(n);vector<int> g(n);//2.初始化f[0] = nums[0];//3.填表for(int i = 1; i < n; i++){f[i] = g[i - 1] + nums[i];g[i] = max(f[i - 1], g[i - 1]);}//4.返回值return max(f[n - 1],g[n - 1]);}
};

---

213. 打家劫舍 II

【题目】：213. 打家劫舍 II

【算法思路】

绘图分析是一种快速的问题分析方法。通过画图分析，我们可以根据第一个位置是否选择，分成两个部分。剩余部分的处理方式与“面试题 17.16. 按摩师”的解法类似，使用简单的多状态动态规划（DP）方法即可解决。

在解决问题的过程中，可以根据一些特殊条件将问题划分为子问题，从而使用相同的逻辑来处理这些子问题，这样有助于简化并有效解决其中可能存在的特殊情况。

【代码实现】

class Solution {
public:int rob(vector<int>& nums) {   int n = nums.size();int ret =max ( nums[0] + rob1(nums, 2, n - 2), rob1(nums,1, n - 1));return ret;}int rob1(vector<int>& nums, int left, int rigth){if(left > rigth) return 0;//1.创建db表int n = nums.size();vector<int> f(n);auto g = f;//2.初始化f[left] = nums[left];//3.填表for(int i = left + 1; i <= rigth; i++){f[i] = g[i - 1] + nums[i];g[i] = max(f[i - 1], g[i - 1]);}return max(f[rigth],g[rigth]);}
};

---

740. 删除并获得点数

【题目】：740. 删除并获得点数

【算法思路】

有些题目可能需要预处理，才能更容易发现使用动态规划（DP）来解决问题。例如，在这道题中，直接从题目入手使用DP并不可取。我们需要删除 nums[i] - 1 和 nums[i] + 1 这些元素，换句话说，要跳过这些无法相加的元素。

同时，题目要求获取最大值，通常在这种情况下，若需要快速查找元素，需要连续下标访问，哈希表是一个常见的选择。但在这里，我们只需要根据数组下标来查找元素，元素代表相加点数，数值为下标方便操作，因此可以用数组的下标值作为哈希表的替代，通过这种方式进行DP操作更加简便。

【代码实现】

class Solution {
public:int deleteAndEarn(vector<int>& nums) {//1.预处理const int N = 10001;int arr[N] = {0};for(auto x : nums) arr[x] += x;//2.创建dp表vector<int> f(N);auto g = f;//3.填表操作for(int i = 1; i < N; i++){f[i] = g[i - 1] + arr[i];g[i] = max(f[i - 1], g[i - 1]);}return max(f[N - 1], g[N - 1]);}
};

---

LCR 091. 粉刷房子

【题目】：LCR 091. 粉刷房子

【算法思路】

属于很典型的简单多状态dp问题，在i位置时候，通过选择颜色，此时的最小花费。dp细分为三种颜色，在该i位置的最小花费，然后跟最近一次状态，写出状态转移方程。三个状态表示相互作用，相互呼应，最后判断最小就行了。这里建议搞个虚拟节点。

【代码分析】

我们可以搭建一个二维数组，其中每个元素代表一个分化的DP表，用来记录在第 i 位置选择某种颜色时的最小花费。

根据分析出的状态转移方程，可以通过另外两个DP表获取前两个状态的最小值，并加上当前颜色的花费，从而计算出当前状态的最小花费。可以将这两个二维数组视作叠加在一起，三个DP表根据状态转移方程共同处理问题，通过这种方式有效地求解最小花费。

感觉面向过程有点难，不如选择面向对象编程，对于这些问题的处理。

【虚拟节点】

虚拟节点需要保证后续填表正确性，那么可以图像结合状态转移方程，决定虚拟节点初始化数值。

【代码实现】

class Solution {
public:int minCost(vector<vector<int>>& costs) {int n = costs.size();//1.多状态 创建dp表vector<vector<int>> dp(n + 1,vector<int>(3));//2.初始化操作dp[0][0] = dp[0][1] = dp[0][2] = 0;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][1], dp[i - 1][0]) + costs[i - 1][2]; }return min(dp[n][1], min(dp[n][2], dp[n][0]));}
};

---

309. 买卖股票的最佳时机含冷冻期

【题目】：309. 买卖股票的最佳时机含冷冻期

【算法思路】

结合上道题经验，遇到状态超过两种，可以使用0，1，2标识不同状态标识，dp[i] [0]、dp[i] [1]、dp[i] [2]表示i位置，巴拉巴拉状态。

常用手段是画出"状态机"分析状态之间转化，方便写出动态转移方程和初始化处理。这里选择以为i位置结束，所表示状态。根据状态机某个位置，结合最近一次位置结合题目分析，写出然后得到当前位置数值，从而得到状态转移方程。

【代码实现】

class Solution {
public:int maxProfit(vector<int>& prices) {int n = prices.size();//1.创建多状态dp表vector<vector<int>> dp(n, vector<int>(3));//2.初始化dp[0][0] = -prices[0];dp[0][1] = dp[0][2] = 0;//3.填表for(int i = 1; i < n; i++){dp[i][0] = max(dp[i - 1][0], dp[i - 1][1] - prices[i]);dp[i][1] = max(dp[i - 1][1], dp[i - 1][2]);dp[i][2] = dp[i - 1][0] + prices[i];}return max(dp[n - 1][1], max(dp[n - 1][2], dp[n - 1][0]));}
};

---

714.买卖股票的最佳时机含手续费

【题目】：714. 买卖股票的最佳时机含手续费

【算法思路】

首先，根据经验和题目要求，得出状态转移方程。然后选择合适的i位置进行状态分析，得到买入状态和可交易状态的表示。

接下来，可以通过关联最近一次的位置来确定状态转移方程，或者绘制状态机图，将所有状态转化过程进行分析。最后，初始化相关位置，通过状态转移方程确定初始位置，并在图中进行分析。

【代码实现】

class Solution {
public:int maxProfit(vector<int>& prices, int fee) {//1.创建dp表int n = prices.size();vector<int> f(n);auto g = f;//2.初始化f[0] = -prices[0];g[0] = 0;//3.填表操作for(int i = 1; i < n; i++){f[i] = max(f[i - 1], g[i - 1] - prices[i]);g[i] = max(g[i - 1], f[i - 1] + prices[i] - fee);}return g[n- 1];}
};

---

123. 买卖股票的最佳时机 III

【题目】：123. 买卖股票的最佳时机 III

【算法思路】

在解决问题之前，我们需要结合题目和样例进行绘图模拟，直观地展示整个过程。在这里，'最多’的含义是指从0到最大范围，而并非一定要选择这么多。

首先，根据’经验 + 题目要求’得到初步的状态表示，并通过 i 位置进行分析。如果发现该状态表示不够充分，可以增加一个位置来表示’完成了多少次交易’。

接下来，绘制状态机并推导出状态转移方程。在处理状态转移方程时，需考虑所有细节。例如，题目中的状态转移方程可能会涉及越界问题，需在初始化过程中解决这个隐含问题。

特别需要注意的是，第一行位置的初始化应为[1, n - 1]并设置为无穷小，以避免不必要的干扰。此外，初始化某些位置时，要确保它们不会影响后续位置的正确计算，或者确保后续位置能够正确更新。

【代码实现】

class Solution {
public:const int INT = -0x3f3f3f3f;int maxProfit(vector<int>& prices) {//1.创建dp表int n = prices.size();vector<vector<int>> f(n, vector<int>(3,INT));auto g = f;//2.初始化f[0][0] = -prices[0];g[0][0] = 0;//3.填表操作for(int i = 1; i < n; i++){for(int j = 0; j < 3; j++){f[i][j] = max(f[i - 1][j], g[i - 1][j] - prices[i]);g[i][j] = j - 1 >= 0 ? max(g[i - 1][j], f[i - 1][j - 1] + prices[i]) : g[i - 1][j];}}int ret = 0;for(int j = 0; j < 3; j++)ret = max(ret, g[n - 1][j]);return ret;}
};

---

188. 买卖股票的最佳时机 IV

【题目】：188. 买卖股票的最佳时机 IV

【算法思路】

首先处理 k 的值，考虑到 k 可能超过所需的总天数，通过数学方法将 k 调整到一个合理范围内。

这道题算法思路同上道题一样，主要画出"状态机"分析状态转移方程，同时需要分析状态转移方程出现的问题。

【代码实现】

class Solution {
public:const int INF = -0x3f3f3f3f;int maxProfit(int k, vector<int>& prices) {     int n = prices.size();       k = min(k, n/2);//1.创建dp表      vector<vector<int>> f(n, vector<int>(k + 1, INF));auto g = f;//2.初始化f[0][0] = -prices[0];g[0][0] = 0;//3.填表操作for(int i = 1; i < n; i++){for(int j = 0; j <= k; j++){f[i][j] = max(f[i - 1][j], g[i - 1][j] - prices[i]);g[i][j] = g[i - 1][j];if(j - 1 >= 0)g[i][j] = max(g[i][j], f[i - 1][j - 1] + prices[i]);}}int ret = 0;for(int j = 0; j <= k; j++) ret = max(ret, g[n - 1][j]);return ret;}
};

快和小二一起踏上精彩的算法之旅！关注我，我们将一起破解算法奥秘，探索更多实用且有趣的知识，开启属于你的编程冒险！