---

1.按摩師

1.題目鏈接

• 按摩師

---

2.算法思路詳解

• 思路：

  • 確定狀態表示 -> dp[i]的含義

    • 選擇到i位置的時候，此時的最長預約時長
    • 本題，狀態表示還可以繼續細分：
      • f[i]：選擇到i位置的時候，nums[i]必選，此時的最長預約時長
      • g[i]：選擇到i位置的時候，nums[i]不選，此時的最長預約時長

  • 推導狀態轉移方程

    • f[i] = g[i - 1] + nums[i]
    • g[i] = max(f[i - 1], g[i - 1])
      

  • 初始化：f[0] = nums[0], g[0] = 0

  • 確定填表順序：從左往右，兩個表一起填

  • 確定返回值：max(f[n - 1], g[n - 1])

---

3.代碼實現

int massage(vector<int>& nums) 
{int n = nums.size();if(n == 0) return 0;vector<int> f(n);vector<int> g(n);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]);
}

---

2.打家劫舍 II

1.題目鏈接

• 打家劫舍 II

---

2.算法思路詳解

• 思路解析：本題比打家劫舍Ⅰ只多了環形問題，那么只需將環形問題分類討論(依據nums[0])，拆解為兩個線性的打家劫舍Ⅰ問題即可
  • 第一個位置偷：nums[0] + _rob[2, n - 2] <— 第二個位置和最后一個位置不偷
  • 第一個位置不偷：_rob(1, n - 1) <— 偷第二個位置和最后一個位置
• 思路：

  • 確定狀態表示 -> dp[i]的含義

    • 到i位置的時候，此時的最大金額
    • 本題，狀態表示還可以繼續細分：
      • f[i]：偷到i位置的時候，nums[i]必偷，此時的最大金額
      • g[i]：偷到i位置的時候，nums[i]不偷，此時的最大金額

  • 推導狀態轉移方程

    • f[i] = g[i - 1] + nums[i]
    • g[i] = max(f[i - 1], g[i - 1])
      

  • 初始化：f[0] = nums[0], g[0] = 0

  • 確定填表順序：從左往右，兩個表一起填

  • 確定返回值：max(f[n - 1], g[n - 1])

---

3.代碼實現

class Solution
{
public:int rob(vector<int>& nums) {int n = nums.size();// 分類討論，取兩種情況中的最大值return max(nums[0] + _rob(nums, 2, n - 2), _rob(nums, 1, n - 1));}int _rob(vector<int>& nums, int left, int right){if(left > right) return 0;int n = nums.size();vector<int> f(n); // 選vector<int> g(n); // 不選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]);}
};

---

3.刪除并獲得點數

1.題目鏈接

• 刪除并獲得點數

---

2.算法思路詳解

• 思路解析：本題可以先做一個預處理，將問題轉化為打家劫舍

  • 思路：
    • 打家劫舍要求訪問數組中的數的順序是連續的，但本題原始數組顯然不符合要求
    • 雖然原始數組數值不符合要求，但是經過轉換，數組下標是可以符合順序連續的
  • 做法：
    • 將原始數組中的數，統計到arr中，然后在arr中，做一次打家劫舍問題即可
    • 此時，數值相同的值的和可以被其本身值作為arr的下標索引到 <— hash[x] = sum(x)
    • arr[i]：i這個數出現的總和
      

• 思路：

  • 確定狀態表示 -> dp[i]的含義

    • 到i位置的時候，此時獲得的最大點數
    • 本題，狀態表示還可以繼續細分：
      • f[i]：選到i位置的時候，nums[i]必選，此時獲得的最大點數
      • g[i]：選到i位置的時候，nums[i]不選，此時獲得的最大點數

  • 推導狀態轉移方程

    • f[i] = g[i - 1] + arr[i]
    • g[i] = max(f[i - 1], g[i - 1])
      

  • 初始化：f[0] = arr[0], g[0] = 0

  • 確定填表順序：從左往右，兩個表一起填

  • 確定返回值：max(f[n], g[n])

---

3.代碼實現

int deleteAndEarn(vector<int>& nums) 
{sort(nums.begin(), nums.end());int n = nums.back(); // maxvector<int> arr(n + 1);for(auto& x : nums){arr[x] += x;}vector<int> f(n + 1);vector<int> g(n + 1);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], g[n]);
}

---

4.粉刷房子

1.題目鏈接

• 粉刷房子

---

2.算法思路詳解

• 思路：

  • 確定狀態表示 -> dp[i][j]的含義：i -> 到了哪個位置，j -> 這個位置的哪個顏色

    • dp[i][0]：粉刷i位置的時候，最后一個位置刷上紅色，此時的最小花費
    • dp[i][1]：粉刷i位置的時候，最后一個位置刷上藍色，此時的最小花費
    • dp[i][2]：粉刷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[0][0] = dp[0][1] = dp[0][2] = 0

  • 確定填表順序：從左往右，一次填寫三個表

  • 確定返回值：min(dp[n][0], min(dp[n][1], dp[n][2]))

---

3.代碼實現

int minCost(vector<vector<int>>& costs) 
{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][0], dp[i - 1][1]) + costs[i - 1][2];}return min(dp[n][0], min(dp[n][1], dp[n][2]));
}