---

1.最長遞增子序列的個數

1.題目鏈接

• 最長遞增子序列的個數

---

2.算法原理詳解

• 注意：本題思路和思維方式及用到的方法很值得考究，個人感覺很有含金量，且初見不好理解
• 前置知識：如何在數組中一次遍歷就找出最大值出現的次數？
  • x == maxVal：count++
  • x < maxVal：無視
  • x > maxVal：更新最大值，重新計數

    int maxVal = nums[0], count = 1;
    for(int i = 1; i < nums.size(); i++)
    {if(nums[i] == maxVal){count++;}else if(nums[i] > maxVal){maxVal = nums[i];count = 1;}
    }
    

• 思路：

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

    • 以i位置元素為結尾的所有子序列中，最長遞增子序列的個數
    • 本題狀態標識還可以繼續劃分
      • len[i]：以i位置元素為結尾的所有子序列中，最長遞增子序列的"長度"
      • count[i]：以i位置元素為結尾的所有子序列中，最長遞增子序列的"個數"

  • 推導狀態轉移方程

    • 令j為i前面的任一一個數
      

  • 初始化：vector<int> len(n, 1), count(n, 1)

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

  • 確定返回值：前置知識部分用到的小貪心策略，見代碼

---

3.代碼實現

int findNumberOfLIS(vector<int>& nums) 
{int n = nums.size();vector<int> len(n, 1), count(n, 1);int retLen = 1, retCount = 1;for(int i = 1; i < n; i++){for(int j = 0; j < i; j++){if(nums[j] < nums[i]){if(len[j] + 1 == len[i]){count[i] += count[j];}else if(len[j] + 1 > len[i]){len[i] = len[j] + 1;count[i] = count[j];}}}if(retLen == len[i]){retCount += count[i];}else if(retLen < len[i]){retLen = len[i];retCount = count[i];}}return retCount;
}

---

2.最長數對鏈

1.題目鏈接

• 最長數對鏈

---

2.算法原理詳解

• 預處理：按照第一個元素排序
  • 此時問題就轉化成了最長遞增子序列了
  • 目的：保證當前位置不存在可以連在它后面的數對的后面的可能
• 思路：

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

    • 以i位置元素為結尾的所有子序列中，最長的數對鏈長度

  • 推導狀態轉移方程
    

  • 初始化：vector<int> dp(n, 1)

  • 確定填表順序：從左往右

  • 確定返回值：整個dp表里的最大值

---

3.代碼實現

int findLongestChain(vector<vector<int>>& pairs) 
{sort(pairs.begin(), pairs.end()); // 預處理int n = pairs.size();vector<int> dp(n, 1);int ret = 1;for(int i = 1; i < n; i++){for(int j = 0; j < i; j++){if(pairs[j][1] < pairs[i][0]){dp[i] = max(dp[j] + 1, dp[i]);}}ret = max(ret, dp[i]);}return ret;
}