算法导论（动态规划）——简单多状态

算法思路（17.16）

1. 状态表示：
   在处理线性动态规划问题时，我们可以通过“经验 + 题目要求”来定义状态表示。通常有两种选择：

   • 以某个位置为结尾的情况；
   • 以某个位置为起点的情况。

   本题中，我们选择更常用的方式，以某个位置为结尾，并结合题目要求，定义状态表示如下：

   dp[i] 表示选择到位置 i 时的最长预约时长。

   但是在处理位置 ii 时，我们会面临“选择”或“不选择”的两种决策，因此需要将状态细分为：

   • f[i] 表示选择到 i 位置时，nums[i] 必选，此时的最长预约时长。f[i] 表示选择到 i 位置时，nums[i] 必选，此时的最长预约时长。
   • g[i] 表示选择到 i 位置时，nums[i] 不选，此时的最长预约时长。g[i] 表示选择到 i 位置时，nums[i] 不选，此时的最长预约时长。

2. 状态转移方程：
   由于状态表示涉及两个部分，我们分别分析这两个状态的转移关系：

   • 对于 f[i]：

     • 如果选择 nums[i] 必选，我们只需考虑位置 i−1 在不选择时的最长预约时长，因此：
     f[i]=g[i−1]+nums[i]

   • 对于 g[i]：

     • 如果 nums[i] 不选，则 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])

   这代表在处理到最后一个位置时的最长预约时长。

C++:

class Solution {
public:
 int massage(vector<int>& nums) {
 // 1. 创建⼀个 dp 表 
 // 2. 初始化 
 // 3. 填表 
 // 4. 返回值 
 int n = nums.size();
 if(n == 0) return 0; // 处理边界条件 
 vector<int> f(n);
 auto g = f;
 f[0] = nums[0];
 for(int i = 1; i < n; i++)
 {
 f[i] = g[i - 1] + nums[i];
 g[i] = max(f[i - 1], g[i - 1]);
 }
 return max(f[n - 1], g[n - 1]);
 }
};

Java：

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 < n; i++)
 {
 f[i] = g[i - 1] + nums[i];
 g[i] = Math.max(f[i - 1], g[i - 1]);
 }
 return Math.max(g[n - 1], f[n - 1]);
 }
}

算法思路（213）

本问题是“按摩师”问题的变种，具体而言，它涉及一个“环形”模式，而不是单排模式。由于首尾房屋相连，这使得问题的处理方式有所不同。但我们可以将“环形”问题转化为两个单排问题的求解：

1. 偷第一个房屋：在这种情况下，最高金额为 x。此时由于偷了第一个房屋，不能再偷最后一个房屋，因此只需在区间 [0,n−2] 内进行偷窃。

2. 不偷第一个房屋：在这种情况下，最高金额为 y。此时可以偷最后一个房屋，因此只需在区间 [1,n−1] 内进行偷窃。

3. 最终结果：通过计算上述两种情况的最大值，我们可以得到环形问题的最终结果。也就是说，问题已有效转化为求解两个单排问题的最大值：

   结果=max⁡(x,y)

C++:

class Solution 
{
public:
 int rob(vector<int>& nums){
 int n = nums.size();
 // 两种情况下的最⼤值 
 return max(nums[0] + rob1(nums, 2, n - 2), rob1(nums, 1, n - 1));
 }
 int rob1(vector<int>& nums, int left, int right){
 if(left > right) return 0;
 // 1. 创建 dp 表 
 // 2. 初始化 
 // 3. 填表 
 // 4. 返回结果 
 int n = nums.size();
 vector<int> f(n);
 auto g = f;
 f[left] = nums[left]; // 初始化 
 for(int i = left + 1; i <= right; i++)
 {
 f[i] = g[i - 1] + nums[i];
 g[i] = max(f[i - 1], g[i - 1]);
 }
 return max(f[right], g[right]);
 }
};

Java：

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 <= right; i++)
 {
 f[i] = g[i - 1] + nums[i];
 g[i] = Math.max(g[i - 1], f[i - 1]);
 }
 return Math.max(f[right], g[right]);
 }
}

算法思路（740）

本题实质上是“按摩师”问题的变种。注意到题目描述，当选择某个数字 x 时，x−1 和 x+1 的数值不能被选择。这与“按摩师”问题中的逻辑相似：选择位置 i 的金额后，不能选择位置 i−1 和 i+1 的金额。

因此，我们可以通过以下步骤解决这个问题：

1. 创建哈希数组：

   • 根据题目中的数据范围，创建一个大小为 10001 的哈希数组 hash。
   • 遍历数组 nums，将数组中每个元素 x 的值累加到哈希数组的对应位置 hash[x] 上。有了这个哈希数组，我们能将相同金额的数值进行聚合。

2. 应用按摩师策略

C++:

class Solution {
public:
 int deleteAndEarn(vector<int>& nums) {
 const int N = 10001;
 // 1. 预处理 
 int arr[N] = { 0 };
 for(auto x : nums) arr[x] += x;
 // 2. 在 arr 数组上，做⼀次 “打家劫舍” 问题 
 // 创建 dp 表 
 vector<int> f(N);
 auto g = f;
 // 填表 
 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]);
 }
};

Java：

class Solution 
{
 public int deleteAndEarn(int[] nums) 
 {
 int n = 10001;
 // 1. 预处理 
 int[] arr = new int[n];
 for(int x : nums) arr[x] += x;
 // 2. dp
 // 创建 dp 表 
 int[] f = new int[n];
 int[] g = new int[n];
 // 初始化 
 f[0] = arr[0];
 // 填表 
 for(int i = 1; i < n; i++)
 {
 f[i] = g[i - 1] + arr[i];
 g[i] = Math.max(f[i - 1], g[i - 1]);
 }
 // 返回值 
 return Math.max(f[n - 1], g[n - 1]);
 }
}

算法思路（091）

1. 状态表示：
   在处理线性动态规划问题时，我们可以通过“经验 + 题目要求”来定义状态表。通常有两种选择：

   • 以某个位置为结尾；
   • 以某个位置为起点。

   本题中，我们选择以某个位置为结尾的方法，并结合题目要求，定义状态表示为：

   • dp[i][0]：表示到达位置 ii 时，如果最后一个位置刷上“红色”，所需的最小花费；
   • dp[i][1]：表示到达位置 ii 时，如果最后一个位置刷上“蓝色”，所需的最小花费；
   • dp[i][2]：表示到达位置 ii 时，如果最后一个位置刷上“绿色”，所需的最小花费。

2. 状态转移方程：
   由于状态表示定义了三个状态，我们需要针对每个状态推导其转移方程：

   • 对于 dp[i][0]（最后一个位置刷红色）：

     dp[i][0]=min⁡(dp[i−1][1],dp[i−1][2])+costs[i−1][0]

     这里，我们需要获取位置 i−1i−1 刷蓝色或绿色情况下的最小花费，然后加上当前位置的红色刷费。

   • 对于 dp[i][1]（最后一个位置刷蓝色）：

     dp[i][1]=min⁡(dp[i−1][0],dp[i−1][2])+costs[i−1][1]

   • 对于 dp[i][2]（最后一个位置刷绿色）：

     dp[i][2]=min⁡(dp[i−1][0],dp[i−1][1])+costs[i−1][2]

3. 初始化：
   设定一个辅助节点来帮助我们初始化工作。当我们添加一个辅助节点时，需确保两个关键点：

   • 辅助节点内的值：应保证能正确初始化后续状态表；
   • 下标映射关系：在本题中，我们添加的辅助节点默认设置为 0。

4. 填表顺序：
   根据状态转移方程，应按顺序“从左往右”填充这三个状态表。

5. 返回值：
   最终，我们需要返回在所有颜色情况下的最小花费：

   min⁡(dp[n][0],dp[n][1],dp[n][2])

   这里 nn 表示房屋的数量，确保能够在最后一个位置中选择刷上任一颜色的最小花费。

C++:

class Solution {
public:
 int minCost(vector<vector<int>>& costs) {
 // dp[i][j] 第i个房⼦刷成第j种颜⾊最⼩花费 
 int n = costs.size();
 vector<vector<int>> dp(n + 1, vector<int>(3));
 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][0], min(dp[n][1], dp[n][2]));
 }
};

Java：

class Solution 
{
 public int minCost(int[][] costs) 
 {
 // 1. 创建 dp 表 
 // 2. 初始化 
 // 3. 填表 
 // 4. 返回结果 
 int n = costs.length;
 int[][] dp = new int[n + 1][3];
 for(int i = 1; i <= n; i++)
 {
 dp[i][0] = Math.min(dp[i - 1][1], dp[i - 1][2]) + costs[i - 1][0];
 dp[i][1] = Math.min(dp[i - 1][0], dp[i - 1][2]) + costs[i - 1][1];
 dp[i][2] = Math.min(dp[i - 1][0], dp[i - 1][1]) + costs[i - 1][2];
 }
 return Math.min(dp[n][0], Math.min(dp[n][1], dp[n][2]));
 }
}

算法思路（309）

1. 状态表示：
   在处理线性动态规划问题时，我们可以通过“经验 + 题目要求”来定义状态表。针对本问题，有三种状态：

   • 买入状态；
   • 可交易状态；
   • 冷冻期状态。

   因此，我们可以定义一个三维状态数组 dpdp：

   • dp[i][0]：表示在第 ii 天结束后处于“买入”状态时的最大利润；
   • dp[i][1]：表示在第 ii 天结束后处于“可交易”状态时的最大利润；
   • dp[i][2]：表示在第 ii 天结束后处于“冷冻期”状态时的最大利润。

2. 状态转移方程：
   我们需要根据规则推导状态转移方程：

   • 对于 dp[i][0]（买入状态）：

     • 可以由之前持有股票（保持不变）和今天购入股票（从可交易状态转变）得到：
     dp[i][0]=max⁡(dp[i−1][0],dp[i−1][1]−prices[i])

     其中，dp[i−1][1]−prices[i] 表示在可交易状态下买入股票的利润计算。

   • 对于 dp[i][1] （可交易状态）：

     • 由之前在冷冻期不执行任何交易（停滞）和之前处于可交易状态不执行任何交易得到：
     dp[i][1]=max⁡(dp[i−1][1],dp[i−1][2])

   • 对于 dp[i][2] （冷冻期状态）：

     • 由之前的持有状态卖出股票进入冷冻期得到：
     dp[i][2]=dp[i−1][0]+prices[i]

3. 初始化：
   第一行的状态初始化较为关键，因为后续状态均依赖于第一行值：

   • dp[0][0]：为了处于买入状态，必须在第一天买入股票，故：
   dp[0][0]=−prices[0]
   • dp[0][1]：什么也不做的情况下，利润为0：
   dp[0][1]=0
   • dp[0][2]：进入冷冻期时手中没有股票，利润为0：
   dp[0][2]=0

4. 填表顺序：
   根据状态转移方程，依次从第一天填充到最后一天，三个状态表需要一起更新，方向为“从左到右”。

5. 返回值：
   最后，我们需要返回在可交易状态或冷冻期状态下的最大利润值：

   max⁡(dp[n−1][1],dp[n−1][2])

C++:

class Solution 
{
public:
 int maxProfit(vector<int>& prices) 
 {
 // 1. 创建 dp 表 
 // 2. 初始化 
 // 3. 填表 
 // 4. 返回结果 
 int n = prices.size();
 vector<vector<int>> dp(n, vector<int>(3));
 dp[0][0] = -prices[0];
 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], dp[n - 1][2]);
 }
};

Java：

class Solution 
{
 public int maxProfit(int[] prices) 
 {
 // 1. 创建 dp 表 
 // 2. 初始化 
 // 3. 填表 
 // 4. 返回值 
 int n = prices.length;
 int[][] dp = new int[n][3];
 dp[0][0] = -prices[0];
 for(int i = 1; i < n; i++)
 {
 dp[i][0] = Math.max(dp[i - 1][0], dp[i - 1][1] - prices[i]);
 dp[i][1] = Math.max(dp[i - 1][1], dp[i - 1][2]);
 dp[i][2] = dp[i - 1][0] + prices[i];
 }
 return Math.max(dp[n - 1][1], dp[n - 1][2]);
 }
}